Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

VFix: Value-Flow-Guided Precise Program Repair for Null Pointer Dereferences

作者:Xuezheng Xu, Yulei Sui, Hua Yan, Jingling Xue

单位:UNSW Sydney, University of Technology Sydney

出处:ICSE’19

原文:https://yuleisui.github.io/publications/icse19.pdf


Abstract

自动化程序修复技术(APR:automated program repair)所面临的一个关键挑战就是如何从潜在的无限解空间中有效的寻找正确的补丁。多数已有的方案试图通过推导完整的解空间来寻找合适的补丁。然而,这样的方式通常来说都是不精确甚至是无效的。

文章提出了一种新的由数据流引导的APR方案:VFix,以修复程序中的空指针异常错误(NPE:null pointer exception)。VFix通过推导程序中的数据依赖和控制依赖以缩小解空间的大小,从而更加准确的识别错误相关的修复语句,并生成正确的补丁代码。

文章在Defects4j数据库上对比了VFix与其余8个已有的APR工具。VFix在精度和效率两方面都远远优于其它工具。与这8个工具中最精确的SIMFIX相比,VFix正确修复了3倍数量的NPE错误。VFix正确修复的NPE错误比这8个工具加起来修复的所有错误还要多50%。此外,VFix在几分钟的时间里便能生成正确的补丁,而其它工具则需要几个小时。

1 Introduction

合理的补丁(plausible patch)是指能够通过测试集中所有测试用例的补丁。而正确的补丁(correct patch)则是指对于所有可能的程序输入都能产生正确输出的补丁。

20190520154216

已有的APR方案通常分为以下两个步骤:

  • 错误定位(fault localization):识别一组在失败的测试用例下可能引发错误的修复语句;
  • 补丁生成(patch generation):通过应用预先定义的修复模板来生成修复操作,并再次运行失败的测试用例以验证补丁,此过程不断重复直到生成合理的补丁为止。

基于搜索的方案通常会将所有的修复模板应用于程序中的每一条修复语句,从而导致搜索空间爆炸(search spece explosion)的问题。为了解决这个问题,已有的APR方案通过将补丁根据其优先级进行排序,并设置超时时间,从而缩小需要搜索的解空间的大小。

尽管如此,由于潜在的解空间依旧太大,多数方案依旧需要平均约3至5个小时的不断测试才能修复一个程序中的错误。此外,由于这些方案并不区分错误的类型,同时也不考虑程序中的数据依赖和控制依赖,因此它们往往容易产生不合理的或者合理但不正确的补丁。

空指针解引用错误,即空指针异常错误(NPE),是一种典型的错误类型。由于NPE错误发生的位置与其修复的位置往往跨越了多个函数,因此对于APR工具来说,修复NPE错误一直是一件非常困难的事情。

一直以来,静态分析技术都很少被应用到自动化程序修复这一领域。文章的目的是想通过静态数据流分析,解析程序中的数据依赖和控制依赖,以帮助APR工具缩小需要搜索的解空间的大小。

20190520155659

本文的主要贡献如下:

  • 文章提出了一个由数据流引导的能够精确有效的修复NPE错误的APR方案——VFix,其能够极大的缩小需要搜索的解空间的大小,从而提高生成正确补丁的可能性。
  • 文章基于静态数据流分析以及动态执行的结果来定位错误相关的修复语句,并通过拥塞计算对这些语句进行排序,从而完成错误定位。
  • 文章在Defects4j数据库上对比了VFix与其余8个已有的APR工具修复NPE错误的能力,并进一步使用15个位于4个开源的Apache项目中的NPE错误验证了VFix的有效性。

2 A Motivating Example

VFix通过以下三个步骤生成了与开发者提供的错误修复补丁完全一致的补丁代码:

  • 构造数据流图(constructing a value-flow graph):VFix根据程序的静态数据流切片构造跨函数的数据流图(VFG:value-flow graph);
  • 选取并排序修复位置(selecting and ranking repair locations):VFix从程序的动态切片中收集错误相关的修复语句,并通过拥塞计算对这些语句进行排序,从而完成错误定位;
  • 应用数据流敏感的修复操作(applying value-flow-aware repair operations):VFix基于程序的数据流信息对于错误相关的修复语句生成相应的修复操作。

20190520161717

3 Approach

A. Constructing Static Value-Flow Slices

对于存在NPE崩溃点的程序,VFix构造跨函数的数据流图(VFG),其包含所有潜在的NPE起源点以及其它相关的NPE崩溃点。

20190520163453

函数内的定义与使用关系:$IntraDU(l, l’, v)$,$v$是一个变量或者字段,代表在函数内的控制流路径$P$中,从语句$l$至语句$l’$的关于$v$的定义与使用关系。

函数间的定义与使用关系:$IntraDU(l, l’, a.f)$,代表函数间的控制流路径$P$中,从语句$l$至语句$l’$的关于$a.f$的定义与使用关系。

20190520182015

B. Selecting and Ranking Repair Locations

为了修复NPE错误,VFix只考虑程序的动态切片中存在的修复语句,即程序的静态数据流切片中被动态执行的部分。随后,VFix通过拥塞计算对这些语句进行排序,从而完成错误定位。

20190520182124

此算法的核心思想在于,在拥有更高拥塞值的位置进行修复,更有可能避免其它相关的潜在NPE错误,即那些没有被测试用例发现的NPE错误,从而能够有效的减少生成合理但不正确的补丁的数量。

20190520182215

C. Applying Value-Flow-Aware Repair Operations

NPE错误模型

假设NPE错误发生在崩溃点$v.use()$,大多数在实际程序中出现的NPE错误可以分为以下两种情况:

  • 在某些通向$v.use()$的控制流路径中,$v$没有被初始化;
  • 缺少针对$v.use()$的空检查。

本文只考虑修复上述两类的NPE错误,其它类型的NPE错误,例如违反调用图完整性(call-graph integrity)以及类型完整性(type integrity)的NPE错误,不在本文的考虑范围之内。

修复操作

对于所考虑的两类NPE错误,VFix所采取的所有候选修复操作可以被分为两大类,即初始化(initialization)与跳过(skip)。

VFix共具有6个用于修复NPE错误的修复模板,其中3个是基于初始化操作的模板,另外3个则是基于跳过操作的模板。当对于一条修复语句存在多个修复操作可用时,基于跳过操作的模板将会被首先尝试。

20190520182244

4 Evaluation

作者在SOOT上添加了11.5k行Java代码实现了VFix。VFix基于SOOT内嵌的CFG与调用图在Jimple IR上进行了数据流分析并构造静态数据流切片。此外,VFix使用GZoltar以获取失败测试用例的执行路径,并使用JavaParser解析、分析并转换程序的源代码。

文章使用了两组测试集,包括Defects4j数据库中的4个工程以及4个开源的Apache程序。

20190520192829

20190520192914

VFix生成的补丁只有在通过测试集中的所有测试用例,并且与开发者提供的错误修复补丁在语义或语法上一致的情况下,才能被视为正确的补丁。

20190520193012

VFix在精度和效率两方面都远远优于其它工具。与这8个工具中最精确的SIMFIX相比,VFix正确修复了3倍数量的NPE错误。VFix正确修复的NPE错误比这8个工具加起来修复的所有错误还要多50%。此外,VFix在几分钟的时间里便能生成正确的补丁,而其它工具则需要几个小时。

20190520193055

VFix从通用错误定位工具GZoltar生成的漏洞相关的修复语句中过滤了平均94.11%的无效修复语句,极大的缩小了需要搜索的解空间的大小。

20190520193118

此外,VFix还过滤了平均57%的无效修复操作,进一步缩小了需要搜索的解空间的大小,从而提高生成正确补丁的可能性。

20190520193149