使用自己的代码查找漏洞：检测功能相似但不一致的代码

原文作者：Mansour Ahmadi，Reza Mirzazade Farkhani，Ryan Williams，Long Lu
原文标题：Finding Bugs Using Your Own Code: Detecting Functionally-similar yet Inconsistent Code
原文链接：https://www.usenix.org/system/files/sec21summer_ahmadi.pdf
笔记作者：bight@SecQuan

解决的问题

使用机器学习技术来检测软件漏洞已被广泛应用于研究中。现有作品通常遵循相同的高级概念：对大量已知错误进行训练模型，然后使用经过训练的模型检测相似的错误。但是，这些“从错误中学习”类型的检测技术在实践中使用时面临两个限制:

• 它们通常需要大量已知错误的数据集进行训练，而这些数据集很难收集和清洗。
• 通常必须对模型进行特定类型的错误训练才能取得良好的结果。因此，训练和检测通常仅限于单个错误类型（即特定于错误）。此外，不同的错误类型的检测精度往往会有很大的不同。

论文主要贡献

• 提出了FICS，这是第一个基于漏洞不一致性的漏洞检测方法。它使用两步聚类来检测功能相似但不一致的代码片段。该检测操作在Constructs上进行，Construct是子功能代码的大小可配置的图形表示形式，为方便代码相似性比较而特别定义。FICS还使用了两种新的图形嵌入技术，分别用于两个聚类步骤，使得该工具足够准确且可扩展到大型代码库。
• 作者使用FICS扫描了五个受欢迎的开源项目，包括QEMU和OpenSSL。尽管这些项目中有一些被认为经过了良好的测试，但作者仍以最少的人工工作发现了22个新的独特错误。所有错误均已由其开发人员确认，并随后由开发人员修复。
• 由于缺乏对不一致检测工具进行系统评估的基准，论文提出了一种新颖的开源基准，即iBench。iBench包含22个已知的真实软件错误。论文进一步评估了iBench上的FICS，并证明FICS可以胜过当前的不一致检测方法。

FICS工作流程

FICS的工作流程包含9个步骤。它从过程内数据依赖图提取Constructs。通过两步聚类过程，FICS将相似的Constructs分组，然后在此类组中找到不一致之处。最终，FICS输出了可能是漏洞的功能相似但不一致的Constructs，人类分析人员可以轻松地对其进行分类。

1. 代码表示和粒度

FICS选择PDG作为开发FICS程序表示的基础。之所以选择PDG，是因为它在通用程序表示形式中语义上最全面，因此适合发现和聚类功能相似性的需求。此外，PDG最初是出于程序切片的目的提出的[25]。它们的子图自然地捕获了区域控制和数据相关性，它们是定义Constructs或不一致代码的粒度的理想原语。
FICS的有效性和效率在很大程度上还取决于执行相似性和不一致分析的代码粒度。作者介绍了Construct的概念，并表明它是达到论文目的的适当代码粒度。Construct是DDG的子图，它表示自包含的子例程，该子例程是函数的一部分（例如，处理API调用的参数）。提取出的Construct在概念上类似于程序切片。
给定DDG，提取将从指定的节点（即根）开始并遍历DDG，直到覆盖所有后续节点或达到“Construct最大深度”为止。然后，所有遍历的节点和边构成一个“Construct”。根变量和最大深度唯一地定义了一个Construct。可以选择函数F中使用的任何变量V作为提取Construct C的根变量。在这种情况下，C的根是F的DDG中的节点，其中V是首次定义或使用的（即，当V进入F时）。换句话说，C包含F内部在V上计算或传播V的所有代码语句。最大深度限制了Construct中最长前向路径可能包含的基本块的数量。它是可配置的，并且可以由FICS用户进行调整以限制Construct的深度，因此可以控制确定相似性和不一致性的代码的最大大小。默认情况下，最大深度设置为无限（即，对Construct的深度没有限制）。结果，Construct包含DDG中从根可到达的所有节点和边。我们称这种深度无限的Construct为full-Con。当最大深度设置为有限数n时，Construct在任何前向路径上不能包含n个以上的基本块。这样的Construct体称为n-Con。例如，当n = 1时，一个Construct（即1-Con）仅包含1个基本块，即根；当n = 2时，一个Construct（即2-Con）最多可包含2个基本区块，沿着前向路径。

Full-Con的示例在图b中显示，该示例从图a中提取。提取的1-Con的示例如图c所示。通过以这种方式定义Construct，作者将检测代码不一致的问题概括为在单个数据变量上找到相似且不一致的操作/计算的问题。这种概括允许以通用方式（即，不与特定类型的代码不一致相关联）并且以相对小的代码粒度来检测不一致。
对于程序中的每个函数，FICS会为函数的每个参数和局部变量以及函数可以访问的每个全局变量提取“Construct”。此外，FICS执行Construct抽象，其目的有两个：（1）删除某些对FICS无用的语法信息，这些信息可能对相似性聚类产生负面影响；（2）进一步最小化Construct以实现更有效的聚类。为了抽象化Construct，仅保留每个程序语句的变量类型，并删除所有变量名称和版本2。最后，抽象Construct用作两步聚类的输入。

2. 两步聚类

作者设计了一个两步的聚类过程，首先将相似的构建体分组，然后在每个组中识别不一致的构建体或异常值。使用“双重镜头”类比可以很容易地解释这个高层次的想法：我们使用第一个镜头，其分辨率不是很高，但视野很广，可以检查Construct并确定那些（大致）相似的Construct。然后，我们使用分辨率更高但视野更窄的第二个镜头放大到相似Construct的每个组，并发现成员之间的差异（或不一致）。显然，第一步聚类应该稍微粗粒度并且高效，而第二步聚类应该细粒度并且能够准确地检测出细微但关键的不一致性。
第一步聚类：
为了使第一步聚类在功能上相似的Construct之间具有一定程度的粗化和容差，作者设计了一种定制的图相似性评分方案。为了量化一对Construct之间的相似度，我们计算了它们对应的节点袋嵌入之间的余弦相似度。

具体来说，请考虑中的示例，该示例显示了缺少对数据<10的检查时基于堆栈的缓冲区溢出（CWE121）。漏洞和正确的Construct（即以数据为根变量的full-Con）之间的余弦相似度是根据Construct的节点袋嵌入计算的。计算出的相似度得分为0.96，表明这两个Construct相似，但存在细微差别。在为每对Construct算出余弦相似度后，我们将成对相似度分数输入聚类算法。
聚类算法基于成对相似度得分将相似的Construct分组到程序中。作者选择连接组件算法，它比诸如DBSCAN和Affinity之类的其他算法更简单，并且执行速度更快。该算法首先基于先前计算的相似性得分构建相似性图。然后，它从高度连接的子图上形成聚类。聚类算法的一个重要参数是相似性阈值，可以由FICS用户进行调整。调整此参数将直接影响算法输出的群集的数量和大小。设置的阈值越高，形成的簇越多，并且这些簇趋向于越小，反之亦然。
第二部聚类：
FICS执行第二步聚类，以对从第一步聚类生成的每个聚类的Construct进行分组。尽管我们的节点袋嵌入适用于粗粒度聚类，但它不能满足第二步聚类的需求。这是因为它不考虑“Construct”中的边，因此无法完全捕获“Construct”的结构。例如，对于错误的操作顺序（CWE666）导致的错误，尽管顺序不同，但错误和非错误Construct的节点可以相同（即，相同的节点包嵌入）。因此，需要一种更精确，更详细的图相似度检查方案。
作者在第二步聚类中采用图嵌入，因为它可以在图内核需要手工制作的子结构时自动学习嵌入。图嵌入技术嵌入图子结构或整个图。因为在此步骤中的目标是对图进行聚类，而不是对子结构进行聚类，所以作者使用了graph2vec嵌入，与其他方法相比，graph2vec可以以更有效的方式实现相似或更好的聚类结果。对于相似Construct的每个群集，基于graph2vec嵌入计算每对Construct之间的相似度。然后将相似性分数输入到聚类算法中。对于第二步聚类，需要使用非常高的相似性阈值（即1或非常接近1），该阈值必须对相似Construct之间的细微差异敏感。

3. 偏差分析和过滤

偏差分析：
两步聚类的输出包含相似但不一致的Construct。但是，并非所有这些不一致的Construct都是有害的漏洞。偏差分析可帮助FICS用户审查检测到的不一致之处，以便快速识别出真正的错误。

作者在表2中总结了这种偏差，以指导和促进手动分析和错误分类。尽管清单并不完整，但可以帮助人类分析人员确定潜在的较高漏洞的优先次序。
过滤：
偏差分析使分析人员可以将重点放在高度优先的不一致或极有可能是漏洞的Construct上。过滤步骤将消除冗余或可能错误的不一致性。例如，如果检测到的不一致涉及几个缺失的“ if”条件，则不一致不太可能是真实的或是错误的（即，开发人员很少忘记在一小段代码中执行多次不同的检查）。
过滤步骤使用四个通用和简单的经验规则，以减少或消除虚假或无关紧要的不一致：

• 在不一致报告中，如果不一致集群中的所有Construct都重叠，则忽略报告。当变量在函数中传播到另一个变量时，通常会发生这种重叠，这使得它们对应的Construct看起来很相似。同一功能中此类相似Construct之间的差异通常并不表示不一致或错误。真正的不一致通常发生在不同的功能或编译单元之间。
• 如果不一致的集群包含多个固定数量（例如2个）的偏离节点，则取消不一致的优先级，因为不太可能是真正的不一致（即，单个不一致很少涉及许多偏差）。我们注意到，该规则仅适用于偏离节点，而不适用于Construct中的所有节点。例如，当不一致的地方存在超过10行代码差异，但是其中只有两个是“ if”条件（icmp节点）时，不会触发此规则。
• 如果多次发现相同的不一致，我们只会报告一次。发生这种冗余是因为系统集成了使用不同粒度和相似性阈值生成的报告。
• 如果不一致的簇数大于阈值（在我们的示例中为5），则优先考虑这些簇中的不一致，因为识别出的不一致簇越多，则这些簇代表真实不一致的可能性就越小（即，群集是零散的并且不可靠）。

实验与评估

如表所示，在过滤410个报告之后，FICS报告了82个不一致的情况。论文将FICS与三个相关的错误检测器进行了比较。FICS获得了最高的真实阳性率（86％），并且明显超过了次优（APIsan 27％）。

FICS检测到218个有效的不一致，包括121个潜在的错误（有害的不一致）和95个代码气味（无害的不一致）。到目前为止，在潜在的错误中，有22个已被开发人员确认并修复。分析每个报告不超过2分钟。

FICS，APIsan，LRSan和Crix之间在错误检测功能方面的比较。FICS的表现优于竞争对手，同时没有报告太多潜在案件。（#Rep：报告数量，＃B：错误数量）