3 月 3 日，阿里巴巴算法工程师别象在云效 DevOps 交流群中分享了《阿里巴巴代码缺陷检测探索与实践》。从阿里巴巴代码平台在探索缺陷检测和补丁推荐问题时遇到的挑战入手，介绍了目前业界和学术界较为流行的缺陷检测手段，并针对其局限性，提出 PRECFIX 方法。

目前 PRECFIX 技术已经在阿里巴巴集团内部落地并获得好评；关于 “PRECFIX” 技术的论文被国际软件工程大会（ICSE）收录。

 张昕东 (别象)   阿里巴巴 云研发事业部 算法工程师

【以下为别象分享实录】

阿里巴巴在缺陷检测技术方面遇到的三个挑战

编码是 DevOps 的重要一环，我所在的部门主要负责阿里巴巴集团的代码托管。在平台业务的背后，我们建设了一系列智能化能力用来赋能前线业务。依赖底层的代码图谱和离线数仓（离线数据仓库）的数据能力，代码智能衍生出了缺陷检测、代码生成、代码克隆、代码安全等能力。今天主要介绍一下我们在缺陷检测领域的初步探索和实践。

缺陷检测和补丁推荐几十年来一直是软件工程领域的难题，又是研究者和一线开发者最为关心的问题之一。这里讲的缺陷不是网络漏洞、系统缺陷，而是隐藏在代码中的缺陷，也就是程序员们戏称的 “八阿哥”（即 BUG）。每位开发者都希望有一种智能的缺陷检测技术来提升代码质量，避免踩坑。所谓 “最迷人的最危险”，如此令人着迷的技术自然有着重重阻碍。

在研究了现有的一些解决方法以及阿里巴巴内部数据集的特征后，我们将缺陷检测技术在阿里巴巴产品落地上的挑战归纳为三个方面：

复杂的业务环境

首先阿里巴巴经济体业务种类繁多，有底层系统中间件的代码，有物流的代码，也有安全、人工智能等各个领域的代码，业务在变，代码缺陷类型也在变。代码数据只增不减，代码缺陷类型捉摸不透，缺陷检测的困难不言自明。

以 Java 语言为例，学术界的 Java 缺陷公开数据集常用的是 Defect4J。Defect4J 包含 6 个代码库，有将近 400 个人工确认的缺陷和补丁。这些代码库是比较基础常规的代码库，缺陷种类容易划分，一部分研究者也做了特定缺陷种类的研究，对症下药效果尚可，然而换了一种缺陷类型，那么检测的效果就很难令人满意了。

在阿里巴巴数据集中，有众多的缺陷类型难以定义，希望能有一种对缺陷类型泛化能力强的缺陷检测与补丁推荐的方法，不说 “包治百病药到病除”，但希望能够适应不同的 “病症”，提高代码 “免疫力”。

有限的辅助资源

第二大挑战来源于有限的辅助资源，这也是导致许多学术界相关成果无法直接复现利用的原因。

何谓辅助资源，常用者有三：测试用例，缺陷报告，缺陷标签。

虽然大多数线上代码都已经达到了很高的测试覆盖率，但是由于代码质量参差，有一大部分代码库是缺乏测试用例的，我们也缺少足够的缺陷报告去直接定位缺陷。我们也想尝试过通过缺陷标签来学习缺陷模式，然而自动打标签的方法准确率不高，而人工给如此庞大的数据集打标签是不太现实的。

产品落地的要求

而最难现实的是第三大挑战，来自产品的落地要求。

作为一项技术，需要在产品中寻找落地的机会。而真实的落地又对技术有极高的要求：我们构想的主要落地场景是代码评审中的缺陷静态扫描及补丁推荐。产品经理说：“检测过程要高效，尽量不要给误报，定位缺陷还不够，补丁方案还得让用户知道。”

业界和学术界较为流行的缺陷检测手段和其局限性

搞研究做创新自然不能固步自封，闭门造车。我先来给大家简单地介绍一些相关领域的一些现有成果。

主要从缺陷检测，补丁推荐，以及其他相关的技术应用三个方面做介绍。

缺陷定位技术

关于缺陷定位技术的这些归纳总结主要来自于熊英飞老师（北京大学新体制副教授）的论文。主要方法大类有：基于光谱的缺陷定位，基于突变的缺陷定位，堆栈分析等等。

比如基于光谱的缺陷定位是基于测试用例，通过的测试用例经过的代码行给予正向分数，失败的测试用例经过的代码路径给予负面分数，类似于光谱的形式将分数较低的一些代码行归类为潜在缺陷行。

这些缺陷定位手段大多关注特定缺陷，在定位某些特定缺陷时准确率明显高于其它缺陷，比如 Predicate Switching 主要用于检测条件语句中的 bug。

第二个局限在于误报率较高，以 Defect4J 数据集测试结果为例，以上方法中准确率最高的是基于光谱的定位，但是 TOP1 的命中率也只有 37% 左右。有研究工作将这些各有所长的缺陷定位手段整合起来一起判断，但误报率仍然高于 50%。

最重要的一点是，上述的缺陷定位手段不提供补丁信息，这一点在实际应用过程中是很致命的，比如基于光谱的定位会返回多个潜在缺陷行，但是没有明确的修复方案，用户会比较迷茫。

补丁推荐技术

关于补丁推荐技术，比较具有代表性的研究是 Generate-and-validate approach，这种类型下的研究成果大体思路是基于失败的测试用例，定位到代码上下文，然后通过随机替换代码元素，或基于语义不断尝试改变抽象语法树上的结点，并利用测试用例或其它可验证信息去验证修改的结果，直到测试用例或其他验证手段跑通。
这些补丁生成的方法主要有三大局限，首先是准确率低，主要体现在 Overfitting（过度拟合）问题上，意思是生成的修复片段和现实中工程师实际的修复方式不同，有些修复甚至是面向测试用例的修复而不是面向真实缺陷的修复。左图是某论文中一个 Overfitting 的例子，“Generate-and-validate” 方法将 if 条件修改为了一个无意义的恒等于 true 的条件，使得该方法每次安全地 return，这样的修改确实能跑通测试用例，但是对真实的 bug 是无济于事的。

第二个明显的局限是耗时长，消耗的计算资源较多，这种修复方法往往是小时级的，而且他是基于编译的，需要不断地测试运行，效率较低。

此外，这种方法对测试用例完备性的要求非常高，它既考验测试的覆盖率，又考验了测试用例设计的合理性。

其它应用技术

还有一些缺陷检测或补丁推荐技术，可能大家有所耳闻，特别是 Facebook 和 Google 的，我也简单地介绍下。
Simfix 和 CBCD 主要是基于缺陷报告的补丁生成，利用代码克隆把缺陷报告和补丁迁移到新代码上。
Ubisoft 的 CLEVER 首先基于特征做了 commit 级别的缺陷预测，对风险较大的一些 commit 做二次检测，二次检测的方法是将缺陷报告根据代码的 dependency 聚类起来，然后做抽象语法树的节点相似度比较，游戏代码往往有一些相似的缺陷。
Bugram 是将代码解析成 token 序列，利用 Ngram 算法来预测出现某一个 token 的概率，概率低的 token 可能是个缺陷点，这种方法当代码复杂度变高或代码词汇数量过大后，效果就急剧下降。
Infer，Getafix，Sapfix 都是 Facebook 提出的，做的都很不错。Sapfix 主要是针对移动手机的 UI 做类似 Fuzzing 的缺陷检测，Infer 主要针对代码的 NPE 问题做了偏规则的检查，所以准确率较高，Getafix 是在 Infer 的检测结果的基础之上，对工程师修复的补丁做了模式聚类，将常用的 NPE 修复模式统计生成出来。
Tricorder 和 Findbugs 等工具都是比较成熟的代码检测器，开发者可以基于这之上定制自己的检测机制，但比较依赖规则的人工制定。
我们为什么提出 PRECFIX 方法

经过调研后，我们发现外部的已有技术方法不能完全解决阿里巴巴面临的挑战和问题，于是我们提出了 PRECFIX 方法 (Patch Recommendation by Empirically Clustering)。

我们首先在阿里巴巴数据集中复现了一个基于特征工程的 commit（代码提交）级别缺陷风险检测，这个在之前讲 Ubisoft 的 Clever 的时候有提过，具体方法是从代码数据集中根据托管系统 Git 建立 commit 父子关系图，利用改进的 SZZ 方法对 commit 进行自动打标签，然后抽取出一部分特征如下所示，然后利用 Xgboost 或者随机森林（Random Forest）对特征和标签进行训练，将模型用于 commit 风险的检测。特征主要分为规模、代码分布、目的、开发者经验以及文件修改五大维度，共 14 个子特征。

以 SZZ 算法作为标签数据的模型在准确率上有瓶颈。SZZ 算法虽然逻辑合理，在公开数据集上有比较好的表现，然而在我们的代码数据集上，准确率不高，人工观察了数百条 SZZ 算法标注的缺陷 commit，其中仅有 53% 是真实的修复行为。“噪声点” 主要来自以下几种场景：业务型的修复与代码无关，注解日志的改动，测试类的调整，代码风格的优化，代码改动本身是用于 “debug” 的所以 message 中带有 “debug” 信息等等。而更进一步，仅有 37% 的修复型代码改动可以迁移到新的代码上，这也就意味着有些代码改动虽然是真实的修复，但是由于改动量过于复杂，或者只与特定环境，特定上下文相关，没有可借鉴的价值。

通过对标签数据的细致分析，我们认为自动化的标签不满足我们的需求，而且打缺陷标签对打标者的技术要求较高，对海量的代码改动历史打标签也是不现实的。

我们开始不盲目寻找和复现方法，而是用心去感受和发现开发者在日常开发过程中的修复行为，我们总结了以下几点：首先，借鉴于 SZZ 算法，commit message 中往往包含了用户的修复意图，可以依据 commit message 来过滤出一部分数据。另外我们在调研 SZZ 算法数据时，发现 75% 的修复提交都有这样的模式：删除一些缺陷代码,然后新增一些代码，比如修改了一个参数，在 diff（差异文件）中便是删除了一行，新增了一行。

还观察到一个细节就是一个修复的操作往往涉及的文件数不超过两个，而一些不太规范的 commit 里面含有大量的文件，即使里面包含了修复行为，也会被稀释掉，引入不被欢迎的噪音。

同时我们也调研了在代码评审阶段用户比较关心的缺陷，如故障点、重构点、代码风格、性能问题等等，很多问题都有重复出现、重复修改的记录。我们萌生了从海量的提交历史中挖掘出重复常见的缺陷，防止开发者再次犯错的想法。

于是我们提出了 PRECFIX，Patch Recommendation by Empirically Clustering，也是这次 ICSE 收录的论文中描述的方法,后期会在云效产品中使用。其实思路方法比较直接简洁，主要分为三步，首先从代码提交数据中提取 “缺陷修复对”，然后将相似的 “缺陷修复对” 聚类，最后对聚类结果进行模板提取，这个缺陷检测和补丁推荐技术可以用于代码评审，全库离线扫描等等。用户的反馈以及我们人工的审查可以进一步提高模型推荐质量。

实现 PRECFIX 方法的技术细节

接下来我们聊一下实现 PRECFIX 方法的技术细节。首先是 “缺陷修复对提取”。有朋友可能会有疑问，何为 “缺陷修复对”？“缺陷修复对” 如何提取？

缺陷修复对提取

这得先从几个数字讲起。SZZ 算法利用 Blame 信息去追溯引入缺陷的 commit 以及缺陷行，我们观察发现，有 25% 的文件的缺陷行源自多个文件，这就意味着利用 blame 信息去溯源可能会将一个缺陷追溯到两个源头，而将一个缺陷的代码行一分为二很有可能是没有意义的。

通过 blame 信息去追溯缺陷代码行不够准确，而我们想要的缺陷相关的代码上下文实际上就是这次修复型 commit 提交前该文件最后一次提交的内容，我们可以直接通过本次提交的文件和对应的 diff 还原出本次提交前的文件内容。

我们发现，大多数的修复行为是以方法为单位的，所以我们提出了以方法为单位的 “缺陷修复对” 提取方法，即将方法体内的 diff chunks（差异文件区块）合并，生成一个缺陷修复对。当然也可以不以方法体为范围，直接以 diff chunk 为单位去提取缺陷修复对，这些都各有利弊，如果以 diff chunk 为单位去提取，那就不需要源代码信息了，直接解析 diff 即可。

在提取过程中有个小 tips 就是将缺陷片段和修复片段归一化，比如将空格和换行符去掉，然后比较两者，将相同的缺陷修复对过滤掉，这样能过滤掉一部分代码格式修改。

我们发现 60% 的 commit 仅包含了 1-2 个文件，但也存在小部分的不规范 commit 包含了数十个甚至上百个文件。如之前所说，我们认为一次修复行为关联的文件往往在三个以下，为了减小噪声的引入，在提取缺陷修复对的过程中建立过滤机制。其实这个 commit 文件数量的限制是准确率和召回率的权衡，在真实实践中我们为了召回率略微放宽了限制，将阈值设为了 5。

通过 SZZ 算法标注的代码缺陷 47% 不够准确。我们沿用了 SZZ 的利用 commit message 的数据采集步骤，所以这个缺陷修复对的提取过程还是会存在大量的噪声难以去除。我们想到了聚类，将常见的缺陷与补丁聚类起来，总结成模板，一些噪声或没有借鉴意义的缺陷修复会被自然地过滤。

缺陷修复对聚类

提取完缺陷修复对后，为了尽量减少噪音，并且我们的目的是提取共性缺陷修复记录，于是采用了聚类的方法，将相似的缺陷修复对聚类在一起，得到一些共性的缺陷。

由于事前无法预测类簇数量，我们没有使用 Kmeans 聚类算法，采用了目前比较成熟的基于密度的 DBSCAN 算法，当然也可以使用 pairwise 的比较和合并，也就是所有情况都比一遍。

聚类方式上，我们尝试过很多种，有单独聚类缺陷片段的，效果不错，但是修复片段的分析成为了难点，因为同样一段缺陷片段有不同的修复方案，很难自动化地分析。我们最后尝试了同时聚类缺陷和修复片段，这样聚类的方式可以在匹配上缺陷片段时直接给出修复片段，不用再另外考虑如何做修复推荐。

直接使用 DBSCAN 效率较低，以我们的实验数据量来讲，大概需要 70 个小时。于是，我们在 DBSCAN 的基础上做了一定的优化，主要有图表上的几种方式。我们基于 MapReduce 实现聚类，Mapper 阶段做缺陷修复对的预处理，Reducer 阶段跑 DBSCAN。第一种优化方式是在 Mapper 阶段采用 KDTree 或者 SimHash 算法将比较相近的缺陷修复对分发到一个 Reducer 中做并行聚类，时间性能大概提升了 4 倍。类簇损失率主要是和基础版的 DBSCAN 算法相比，大概损失了 6%。

大多数的缺陷修复对互相之间是没有任何关联的，而我们利用代码克隆技术比较两个片段又是最耗时的部分，图上的 APISEQ 便是我们优化 “不必要比较” 的方法。我们洞察了这批缺陷修复对数据集，发现几乎所有的片段都或多或少包含了方法调用，没有方法调用的片段大概率是一些无意义的噪声，所以我们可以在聚类比较的过程中先比较两个片段是否含有相同的 API，如果有的话再进行比较，通过这个方法时间性能又提高了四倍。

我们也尝试了比较新颖的并行 DBSCAN 算法，速度非常快，但是类簇损失相对较大。这个数据处理的过程是定期的离线计算，频率较低。最终权衡之下，我们选择了耗时相对较短，损失率较小的 KDTree 或 APISEQ+KDTREE 的聚类方法。

至于聚类过程中的两个片段的代码克隆比较方式，我们发现两种互补的计算方式的结果明显优于单个计算方式，我们的最佳实践是 “编辑距离” 和 “Jaccard” 的加权平均，因为 “编辑距离” 能够捕捉到 token（代码元素）的顺序关系，而 Jaccard 能计算 token 重合比例。

模版提取与匹配

最后是 “模版提取”：为了提升用户体验，我们希望将同一类簇的片段聚合起来提取出模板，降低用户的理解成本。

如上图所示，同一类簇的两个片段非常相似，我们先递归地使用最长子序列算法，黄色部分为匹配的内容。一些不匹配的内容除了左边的片段多了一句以外，其他部分实际上是变量名不同，我们将不同的变量名分析提取出来，存储为 “@Para” 的格式方便后期匹配。

当扫描到新的缺陷片段时，我们基于模板识别出它的变量名，并直接用新的变量名替换补丁模板中的 “@Para” 参数，然后自动推荐出带有新参数的修复建议。

下面来看几个 PRECFIX 聚类得到的模板。第一大类是 “合理性检查”，修复片段做了长度的判断，合理性检查也包括了空值检查。

第二个类是 “API 变更”，API 的参数发生了改变，增加了 Gpu id，第一个参数的来源也做了修改。API 变更还包括了方法名的改动，参数的增删改，这是非常常见的类型。

还有一个大类是做查看聚类结果之前没想到的，就是 “API 封装”，工程师往往会把功能独立，经常复用的代码段封装起来，减少代码重复度和维护成本，而且工具类会将方法写的比较完善，减少开发者在编写时产生的不必要的失误。

当然 Precfix 也不是代码缺陷的特效药，只是提供了一种从代码库中挖掘缺陷的思路。模板数量和误报率需要持续地跟进和维护。

PRECFIX 方法已经在阿里巴巴集团内部落地，在内部公开库中扫描出了 800 多种缺陷类型，3 万多个缺陷，并将结果对用户进行了访谈，获得了普遍的好评。后续，该方法也会在 “云效” 产品中应用，供更多开发者使用。

以上内容来自别象在 “云效开发者交流群” 中的视频直播课程，您可以钉钉搜索群号（23362009）入群，收看视频回放。

关于云效：

云效，企业级一站式 DevOps 平台，源于阿里巴巴先进的管理理念和工程实践，致力于成为数字企业的研发效能引擎！云效提供从 “需求->开发->测试->发布->运维->运营” 端到端的在线协同服务和研发工具，通过人工智能、云原生技术的应用助力开发者提升研发效能，持续交付有效价值。