引用：Zhong H, Wang X. Boosting complete-code tool for partial program[C]//Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering. IEEE Press, 2017: 671-681.

摘要：

为了提高软件质量，研究人员和从业人员已经提出了各种用途（例如，检测bug、异常和漏洞）的静态分析工具。尽管存在许多功能强大的此类工具，但是它们通常需要完整的程序，其中所有的代码名（例如，类名和方法名）都被解析。但是在许多场景下，比如研究人员在bug修复（修改后的文件可以看作部分程序）、教程阅读和代码搜索结果中不得不分析部分程序。因此，尽管现有的完整程序分析工具的语法准确，但它们不能分析部分程序，同时现有的部分程序分析工具在数量和分析能力方面都有局限。我们没有提出另一种分析部分程序的工具，而是提出了一种通用的方法： Grapa，它改进了现有的用于完整程序分析工具用于分析部分程序。我们的主要观点是，在解析了未知的代码名之后，用于完整程序分析的工具可以在进行少量修改的情况下分析部分程序。特别的，Grapa定位Java归档文件来解析未知的代码名，并通过解析出来的代码名来解析剩下来的未知代码名。为了说明Grapa，我们实现了一个工具，它利用了最先进的工具WALA来分析Java语言的部分程序。我们因此实现了第一个工具，它能够为部分程序构建系统依赖图补充到现有的工具。我们对来自4个流行的开源项目的8198个部分代码提交进行评估。我们的评估结果显示，Grapa完全解析了98.5%的bug修复中的未知代码名，准确率高达96.1%。此外，我们的结果显示了Grapa内部技术的重要性，它提供了如何与更多的完整代码分析工具集成以分析部分程序的观点。

介绍

部分程序是完整程序的子集。部分代码分析[1]在很多只有部分代码的场景下是必不可少的，比如挖掘用于自动打补丁、缺陷预测的bug修复、分析论坛帖子和软件文档进行代码推荐以及代码搜索结果排序。在本文中，我们遵循Dagenais和Hendren[1]对部分代码做出的定义，要求部分程序中没有语法错误。

定义1（部分程序）：给定一个完整程序< Src, Dep >，其中Src是可编译源代码的集合，Dep是已编译的依赖文件的集合，部分程序是Src的一个子集。

此定义与大多数应用程序场景一致，如分析代码修复、代码搜索结果、文档中的示例等，其中的源文件是不完整的,但是没有语法错误。

尽管部分程序的语法一般是正确的，编译部分程序是不可行的，因为它引用的代码声明可能是得不到的。因为多种原因，研究者已经提出了很多分析部分程序的方法。然而，这些方法存在3个限制。第一，大部分代码工具是不通用的。例如，Zhong等人[2]提出的MAPO可以挖掘推荐代码示例的声明。Mishne等人[3]批评MAPO不能挖掘部分程序的声明。为了解决这个问题，Mishne等人[3]提出PRIME方法，在挖掘声明的时候，将其他调用序列中的未知方法调用与已知方法调用作比较。尽管PRIME能够挖掘部分程序的声明，但是因为一些其他的原因，PRIME不支持部分代码分析。第二，因为分析部分程序很困难，部分代码分析通常是不准确的。例如，Mishne等人承认他们的方法只是相对精确。第三，现有的部分代码分析工具不支持复杂分析。例如，尽管图可以为代码比较提供丰富的信息，Kim和Notkin[4]抱怨基于CFG的方法不能分析部分程序。

方法概述

我们注意到许多完整代码分析工具（如WALA[1]）是构建在成熟编译器（如Eclipse JDT）的基础上的。因为部分程序是不完整的，编译器在解析未知代码名的时候通常会失败。当完整代码分析工具遇到未知的代码名时，他们无法产生有意义的结果。如果我们完全解析这样的未知代码名，改进一些完整代码分析工具来分析部分程序是可行的。

定义2（代码名）：对于给定的部分程序P，我们定义P中的代码名，表示为Names(P)并将其作为出现在P中的所有粒度（比如，类/类型，字段，方法和变量）的代码元素的标识符。另外，如果N是变量/字段，我们将解析代码名N定义为其变量类型和N的全名；如果N是一种类型，则将其定义为N的全名；如果N是一个方法，则将其定义为N的标识符。

方法的优点和挑战。我们的新视野带来了一种新的方法，具有如下优点：

优点一。这是一个可以将完整代码分析工具用于部分代码分析的通用工具。部分程序中的未知代码名对于这些工具有不同的影响。我们的方法适用于所有在成熟编译器上构建的完整代码工具，而不是为特定目标（比如API规则挖掘）提出的解决方案。

优点二。这是一种提高部分代码分析准确率的实用方法。因为部分程序包含未知代码片段，部分代码分析工具通常是不准确的。因为它保留了完整代码工具的完整性，我们的策略可以为部分代码分析提供准确工具。

挑战一。解析部分程序中的未知代码名是一个挑战。PPA[1]是目前解析未知代码元素的代码名的最先进的工具，但是我们的研究显示PPA只能完全解析28.7%的代码名。

挑战二。确定未知代码名是否得到了充分的解析是一个挑战。一些完整代码分析工具没有实现复杂代码分析。因为这些工具从来都不涉及代码名，因此改进这些工具是不足以确定未知代码名是否得到了充分解析。相反，尽管我们可以将解析后的部分程序提供给编译器，但编译通过是一个过于严格的标准，因为即使不通过编译从部分程序中生成字节码，也可以进行许多复杂分析。

具体方法

图1（Fig. 1）展示了Grapa的整体架构。Grapa背后的基本想法是提取给定部分程序的上下文代码，并且使用从上下文代码中提取的信息来将完整代码分析技术应用与部分程序。

定义3（上下文代码）：给定一个部分程序（即源文件集合）p，p使用在定义2中定义的一组代码名Names(p)，p的深度为1的代码上下文定义为

其中v是二进制或源码文件。p的完整的代码上下文被定义为Context*(P)，表明将Context¹函数在p上递归的使用，直到结果集合不再变化（即到达固定点）。

通过部分程序和代码上下文的定义，我们可以看到，对于部分程序p，我们的目标是找到Context*(P)，并将其提供给完整代码分析工具（比如，WALA）。上下文代码的理想来源是完整的源代码集合，和部分程序相应版本的所有依赖jar文件。然而，最近的一项研究显示，即使取出整个源文件集，大多数提交也是不可编译的。

在Grapa中，对于一个部分程序，我们使用它属于的软件项目的发行版作为它的上下文代码。因为一个发行版是已经成功编译的，不需要再修复编译错误。一个代码片段可以引用在任何发型版本中都没有出现的代码名。例如，可以在发布一个版本之后添加代码名，并且在发布下一个版本之前删除代码名。此外，一个部分程序可以来自最新发型版之后的代码库，因此所以已发布的版本都是已过时的。所以单独定位上下文代码是不够的，因此我们进一步提出了解决未知代码名的推理策略。

如图1所示，Grapa有以下主要步骤。对于部分程序，Grapa首先搜索包含给定代码段或与之兼容的以编译软件版本。我们将此版本称为给定程序的上下文版本。然后，Grapa从部分程序中抽取AST，解析绑定在AST中的未知类型。为了与完整代码工具集成，Grapa进一步解析了需要分析的部分程序和上下文代码之间的不明确类型。

本文主要贡献

1. 提出了一种具有通用性的改进部分代码分析的研究思路。与其他的用于特定的部分代码分析的方法不同的是，我们的研究思路可以改进许多构建在编译器上的完整代码分析工具，用于部分代码分析。
2. 提出了一个名为Grapa的新方法，可以改进完整代码分析工具用于部分代码分析。它（1）包括一种为部分程序定位上下文版本的技术；（2）通过附加的策略对PPA进行扩展。
3. 制作了改进WALA用于部分代码分析的工具。该工具支持更深入的实证研究，以及更先进的bug检测方法。
4. 使用从4个活跃的开源工具中收集的8198个部分代码中的bug修复对我们的工具进行评估。我们的第一次评估结果显示，Grapa完全解析了未知代码名，从而为98.5%的总代码修复构建了SDGs。我们第二次评估结果显示，在96.1%的bug修复中，我们的代码名解析结果与使用Java编译器对人工构建的完整程序的编译结果相同。总之，与现有的不准确的部分代码工具不同，我们的工具保留了WALA的准确性。

引用

[1] B. Dagenais and L. Hendren, “Enabling static analysis for partial java programs,” in ACM Sigplan Notices, 2008, vol. 43, no. 10, pp. 313-328: ACM.

[2] H. Zhong, T. Xie, L. Zhang, J. Pei, and H. Mei, “MAPO: Mining and recommending API usage patterns,” in European Conference on Object-Oriented Programming, 2009, pp. 318-343: Springer.

[3] A. Mishne, S. Shoham, and E. Yahav, “Typestate-based semantic code search over partial programs,” in Acm Sigplan Notices, 2012, vol. 47, no. 10, pp. 997-1016: ACM.

[4] M. Kim and D. Notkin, “Program element matching for multi-version program analyses,” in Proceedings of the 2006 international workshop on Mining software repositories, 2006, pp. 58-64: ACM.

致谢

此文由南京大学软件学院2018级硕士史洋洋翻译转述。