根据代码不一致性检测Bug的方法

原文标题：Finding Bugs Using Your Own Code: Detecting Functionally-similar yet Inconsistent Code

原文作者：Mansour Ahmadi, Reza Mirzazade Farkhani, Ryan Williams and Long Lu

发表会议：USENIX Security Symposium '21

原文链接：https://www.usenix.org/system/files/sec21-ahmadi.pdf

笔记作者：夏雪冬花@SecQuan

笔记小编：cherry@SecQuan

0x01 Idea

代码Bug检测指的是在代码中检测可能存在的Bug。在代码Bug检测领域使用机器学习技术是一种常见的做法，但是，传统的基于机器学习的代码Bug检测方法存在以下两点主要缺陷：

1. 依赖于大量标记好的数据，而这些数据在实际应用中难以获取。

2. 传统的方法缺乏通用性，通常只能对特定类型的Bug进行检测。

针对以上两点缺陷，作者提出了一种新的基于机器学习的代码Bug检测方法，这个方法仅仅使用被检测的代码库，而不依赖于外部样本训练模型。同时，这个方法不对可检测的Bug类型做出限制，对所有类型的Bug具有泛用性。

作者提出的方法基于含有Bug的代码片段，与该代码库中功能相似的代码但没有Bug的代码片段具有不一致性的观察。如果一段代码片段与该代码库中的另一段代码库具有类似的功能，它们的代码应该具有一致性，若两端代码之间存在不一致，则在某一段代码中可能存在Bug。导致相似代码之间存在不一致的原因有很多，比如大型软件通常由复数开发人员进行开发，不同的开发人员在编写某一段功能代码时可能会引入不一致性。另一个常见的原因在于对于Bug的修复，可能只对代码库中的某一段代码进行修复，而忽略了代码库中功能相似且存在相同Bug的部分。

0x02 Overview

总体来说，作者提出的方法是一个二阶段聚类模型：先将功能相似的代码片段聚类在一起，再对这些代码片段进行不一致性分析。在第一阶段，使用粗粒度的聚类算法，目的是将功能相似的代码片段区分出来，且相对不受代码实现上不一致的影响。在第二阶段则要求使用粒度更细的方法对代码片段中细微且关键的不一致性进行识别。具体框架如下图所示：

在流程的开始，先将源代码编写的文件转换为LLVM Bitcodes，然后使用程序依赖图(PDG)用于代码的表示。考虑到程序依赖图中的数据依赖已经足够用于捕获代码的语义特征，能够识别Bug的产生，为了提高程序分析效率，作者指出可以将程序依赖图中表示控制依赖的边删除，这样图称作是数据依赖图(DDG)。为采用合适的粒度对程序的功能相似性和代码不一致性进行分析，作者提出了Construct这样一个基本结构。Construct从本质上来讲是数据依赖图的子图，代表着代码中功能相对独立的子程序。通过采取粗粒度和细粒度的方式计算Construct之间的相似度评分并进行聚类，就可以区分出那些功能相似，实现上却存在不一致的代码片段。最后再使用人工分析的方式对识别出来的代码片段对进行分析，可以以较为高效的方式发现代码中存在的Bug。

0x03 Evaluation

Controlled Experiment

作者使用所提出的工具FICS与同类Bug发现工具在包含5处程序中22个Bug的人造数据集上进行对比实验，实验结果如下：

在进行对比的工具中，FICS的真阳率是最高的，达到了86%，在假阳率方面，FICS虽然是对比的四个工具中仅此于Crix的，但也达到了76%。考虑到FICS产生的报告比较容易进行分析，以及可以通过过滤的方法进一步降低假阳率，仍然可以认为FICS是有效的。同时，从实验结果可以看出，FICS在对几乎所有类型的Bug都有发现能力，这体现了FICS的泛用性。

Discovered Unknown Bugs

在对未知Bug的发现上，FICS也有着不错的能力，在对QEMU，OpenSSL，wolfSSL，OpenSSH以及LibTIFF5个代码库进行扫描后，得到了22个受开发者认证的漏洞，在与同类工具对比上具有优势。

0x04 Limitations

论文中提出的检测工具是根据代码库中功能相似但实现不一致的代码片段来对Bug进行检测，若具有Bug的代码片段在代码库中不存在没有Bug的功能相似片段，则无法进行检测。这就要求被检测的代码库需要足够大，若代码库中所含的代码量太小，会严重影响检测的结果。同时，FICS还无法对太小Bug进行检测。因为FICS所操作的基本单位是完整的基本块，对于这些小错误来说，可能显得太大了。