Paper

MVP: Detecting Vulnerabilities using Patch-Enhanced Vulnerability Signatures：USENIX 2020，Yang Xiao et al.

Abstract

重复漏洞（Recurring Vulnerability）广泛存在于真实的系统中，这些漏洞通常由可重用的代码库或共享的代码逻辑导致，因此同样的漏洞很可能在其他地方也存在而未被发现。本文提出了一种新的方法MVP来检测具有低假阳性和低假阴性的重复漏洞，首先利用新的程序切片技术从漏洞函数及其补丁函数中提取漏洞和补丁的语法和语义特征。如果目标函数匹配漏洞特征，但不匹配补丁特征，则该目标函数会被识别为存在漏洞。

本文在10个开源系统上对MVP方法进行实验，结果表明，MVP显著优于目前的基于克隆和基于功能匹配的重复漏洞检测的SOTA方法；MVP检测到了通用的漏洞检测方法无法检测到的重复漏洞；MVP检测到97个新的漏洞，并获得了23个CVE认证。

Introduction

由于软件系统中代码库的重用或代码逻辑的共享(对不同用途的相似对象使用相似的处理逻辑)，使得具有相似特征的重复漏洞广泛存在，但在现实程序中却无法检测到，因此，重复漏洞检测得到了广泛的普及。本文的目的就是检测重复出现的漏洞，也即给定一个在程序中以一种特定的方式运行的漏洞，检测其他程序是否可能存在这种同样形式的漏洞。

现有的检测重复漏洞的方法可以分为两种：

• 一种是基于代码克隆的方法，该方法将重复漏洞的检测问题视为代码克隆的检测问题，从已知的漏洞中提取token或语法级的signature，并将该signature的克隆代码视作漏洞。
• 另一种是基于函数匹配的方法，该方法不考虑任何漏洞特征，直接将已知的漏洞函数作为signature，检测是否存在这些signature的克隆函数。

该领域目前存在的两个主要挑战是如何区分已经修补完成的漏洞，减少假阳性率；以及如何精确的生成一个已知漏洞的signature，来减少假阳性和假阴性。

本文提出了一个针对重复漏洞的漏洞检测方法MVP，为了解决第一个挑战，MVP不仅生成漏洞的signature，还同时生成补丁的signature。利用漏洞特征来检测可能存在的漏洞，并利用补丁特征来区分这些漏洞是否已经打过补丁。为了解决第二个挑战，我们提出了一种新的切片方法，只提取与漏洞和补丁相关的语句，在语法和语义级别生成更加精确的漏洞和补丁的signature。此外，我们采用语句抽象和基于熵的语句选择来进一步提高MVP的准确性。

本文在10个C/C++开源项目上对MVP方法进行了实验，发现了97个尚未被发现的安全漏洞，并获得了23个CVE认证。同时，将MVP与四种现有的SOTA方法进行比较，发现MVP在准确率上明显更胜一筹。

Motivation

本文在10个项目的34019对漏洞和补丁函数上进行了实验，使用SourcerCC同一对漏洞函数和补丁函数的相似度，发现有91.3%的样本对二者相似度均超过了70%，而实验证明有35.1%的真实漏洞目标函数与原漏洞函数的相似度小于70%，所以很难通过仅仅计算目标函数与漏洞函数的相似度来判断是否有漏洞，还要计算目标函数与补丁函数的相似度来综合判断。

Method

上图是本文MVP模型的Framework架构图，一个以函数为检测粒度的重复漏洞检测框架，主要包含以下3个步骤：(以下用“sig”代指“signature”)

• 生成目标函数的sig：输入待检测的目标系统，为系统中的每个目标函数生成sig。
• 生成漏洞代码和补丁代码的sig：输入安全补丁程序，生成漏洞和补丁的sig，从漏洞产生和漏洞修复的角度反映漏洞，得到一个具有众多漏洞和补丁sig的待匹配集合。
• 将目标系统中的每个函数的sig与漏洞和补丁sig进行匹配：如果在待匹配集合中发现了与目标函数sig相匹配的漏洞sig，但不存在相匹配的补丁sig，则认为目标函数存在重复漏洞。

接下来进行详细解读。

首先，定义函数签名，给定一个C/C++函数f，将f的签名定义为一个元组(fsyn，fsem)，其中fsyn是函数中所有语句的哈希值的集合；fsem是由一系列3元组(h1，h2，type)构成的集合，h1和h2表示任意两个语句的哈希值，type ∈\in\in {data，control}表示哈希值为h1的语句和哈希值为h2的语句具有数据依赖或控制依赖关系。fsyn捕获目标函数的语句作为语法签名；fsem捕获目标函数语句之间的数据依赖和控制依赖关系，作为语义签名。二者提供了一个函数的补充信息，以帮助提高匹配精度。

其次，使用(fv,pv)来代表一对漏洞函数和对应的补丁函数。给定一对(fv,pv)，函数Patch Pv由一个或多个hunk（块）组成。hunk是Patch中的一个基本单元，它由上下文行、已删除的代码行和已添加的代码行组成。删除的行在fv中，但不再pv中；添加的行不在fv中，但在pv中。

• 生成目标函数的signature

该过程有3个步骤，首先是parsing过程，使用Joern来parse代码生成代码属性图（一个AST、PDG、CFG联合的数据结构），以获取目标系统的所有函数，对每个目标函数生成AST和PDG。然后对函数做规范化处理，对形参、局部变量和字符串常量替换为同一形式，删除所有注释、大括号、tab、空白。

最后，进行函数签名的生成，首先对规范化后的函数中的每个语句计算hash值，得到fsyn。接着从函数的PDG中提取两个语句之间的数据和控制依赖关系，每一组关系表示成一个三元组的形式(h1，h2，type)，下图展示了一个从原始目标函数到生成sig的完整过程。

• 生成漏洞代码和补丁代码的signature

给定一对(fv,pv)和Patch Pv，下面阐述如何生成sig来捕获与漏洞相关的关键语句，而不是将fv和pv中的所有语句都包含在内，以此获得小而准确的sig来进行有效匹配。

首先识别代码变化，通过解析安全补丁的头文件（diff文件）来识别更改的文件，通过解析diff文件来查找已删除和添加的语句及其行号。同时找到所有函数的起始和结束地址，如果一个语句包括一个或多个已删除（已添加）的代码行，则认为该语句已删除(已添加)，通过比较语句行号和函数行号的关系来确定哪些函数被更改。以此可以获得已添加的语句集合 SaddS_{add}S_{add} ，已删除的语句集合 SdelS_{del}S_{del} ，漏洞函数语句 SvulS_{vul}S_{vul} ，补丁函数语句SpatS_{pat}S_{pat} 。

利用切片技术可以提取相关的语句并排除无关的语句，本文在PDG上执行前向和后向切片，使用SaddS_{add}S_{add}和 SdelS_{del}S_{del} 作为切片的标准。传统的程序切片方法存在一定的问题，比如下图的例子，如果将第18行的条件语句作为切片标准，那么前向切片包含了太多的语句(19-40)，其中会包含很多与该漏洞无关的噪声语句，而如果将标准严格到与18行直接相关的前向切片，则只有23和24行，真正的漏洞行28行又没有包含在内。也就是说如果要求直接相关，则切片可能不包含漏洞语句，而如果允许间接相关，切片又存在太多的噪声。

再比如说下图的例子，如果以第3行的函数调用作为切片标准，由于其没有返回值，因此只能得到后向切片而无法得到前向切片。

基于以上的问题，本文提出了一种新的切片方法，将SaddS_{add}S_{add}和 SdelS_{del}S_{del} 中的每个语句作为切片的标准。对于后向切片，正常的基于PDG进行后向切片，获取与标准句相数据依赖和控制依赖的所有语句。对于前向切片，根据不同的语句类型执行不同的切片准则：

• 赋值语句：正常按照数据流进行前向切片即可
• 条件语句：前向切片过程中只针对条件语句中使用的变量或参数切片（只考虑数据依赖），只有当这样产生的切片为空时，才考虑控制依赖
• 返回语句：不需要进行前向切片，因为返回值和返回语句与后面的语句无依赖关系
• 其他：包括未使用返回值的函数调用语句，对变量和参数的数据依赖语句切片

（注：上面条件语句和其他语句指的数据依赖并不是严格意义上的数据依赖，而是先回溯到变量和参数的定义语句再求数据依赖，比如上图正常来说第4行和第3行不存在数据依赖，但在上面的语境下是存在的，第4行在第3行的前向切片中）

将SdelS_{del}S_{del}以及其对应的前向后向切片放在一起，构成了 SdelsemS_{del}^{sem}S_{del}{sem} 蕴含着该函数已删除的语句的语义信息， SaddsemS_{add}^{sem}S_{add}{sem} 同理。

接下来分别从语法和语义级别上计算漏洞sig和补丁sig，即(Vsyn,Vsem)和(Psyn,Psem)，漏洞sig与漏洞的产生相关，补丁sig与漏洞的修补相关。

首先是计算Vsyn，SdelsemS_{del}^{sem}S_{del}{sem}包含了漏洞产生的语义信息，但有漏洞的修改过程不涉及删除语句，只有增加语句，因此还要补上与增加的语句数据或控制依赖的原漏洞函数语句，也就是(1)式，然后根据PDG图由Vsyn得到Vsem，由SdelsemS_{del}^{sem}S_{del}{sem}得到Tsem。接着将 SaddsemS_{add}^{sem}S_{add}{sem} 和 SvulS_{vul}S_{vul} 做差集找到只存在于补丁函数中的语句即为Psyn，然后先根据PDG图计算漏洞函数的三元组集F，用T和F做差集就可以得到只存在于补丁函数中的语句（新加的语句）的三元组集Psem。

然而按照上述方式生成Vsyn还是会发现存在噪声，而且发现Vsyn这与删除(添加)语句远的语句更有可能是噪声。因此本文提出了一种基于信息熵的漏洞语句选择方法。

设目标系统中语句的总个数为N，Vsyn中某个语句s在目标系统中出现的次数为n，则信息熵为

Is=−log§=−log(nN)∝1nI_s=-log§=-log(\frac{n}{N}) \propto \frac{1}{n}I_s=-log§=-log(\frac{n}{N}) \propto \frac{1}{n}

对Vsyn中的所有语句的信息熵求和，得到总信息熵 III ，如果 III 高于某一阈值就不断的删除离删除(添加)语句最远的语句，直到低于该阈值，或者直到剩余的语句均为与改动代码直接数据或控制依赖的语句。

接着对Sdel，(Vsyn,Vsem)和 (Psyn,Psem)进行如上文所述的规范化处理和计算hash值，得到漏洞sig和补丁sig，对所有的漏洞补丁代码对处理后得到待检测集合。

• 将目标系统中的每个函数的signature与漏洞和补丁signature进行匹配

那么有了目标系统中每个目标函数的sig(fsyn,fsem)，以及删除的语句Sdel，漏洞的sig(Vsyn, Vsem)，补丁的sig(Psyn,Psem)，根据以下原则判断目标函数是否具有漏洞（与漏洞sig匹配但与补丁sig不匹配），规则有以下5条：

• 目标函数必须包含所有已删除的语句
• 目标函数的签名与漏洞签名在语法层次上匹配（Vsyn和fsyn的交集大于某一阈值）
• 目标函数的签名与补丁签名在语法层次上不匹配（Psyn和fsyn的交集小于某一阈值）
• 目标函数的签名与漏洞签名在语义层次上匹配（Vsem和fsem的交集大于某一阈值）
• 目标函数的签名与补丁签名在语义层次上不匹配（Psem和fsem的交集小于某一阈值）

Evaluation

实验回答以下五个问题：

• Q1：与最先进的方法相比，MVP在检测重复漏洞方面的准确性如何？
• Q2：与最先进的方法相比，MVP在检测重复漏洞方面的开销程度如何？
• Q3：在MVP的匹配过程中，如何配置阈值？
• Q4：语句抽象和语句信息的采样对结果的影响有多大？
• Q5：其他漏洞检测方法检测重复漏洞的性能如何？

本文作者对10个开源的C/C++项目代码进行测试，包含了25377个patch和34,378个有变动的函数，具体数据集如下表所示。

本文将MVP模型与两类SOTA方法进行对比，一类是基于代码克隆的重复漏洞检测方法，比如Redebug和VUDDY。另一类是基于函数匹配的方法，比如SourcererCC和CCAligner。最后还对比了VulDeepecker和Devign这两种方法，都是目前漏洞检测领域非常优秀的方法。

• Q1：与最先进的方法相比，MVP在检测重复漏洞方面的准确性如何？

由上图可见，在10个开源系统上MVP模型的准确率和召回率都大幅领先。

• Q2：与最先进的方法相比，MVP在检测重复漏洞方面的开销程度如何？

由上图可见，该类方法都可以分为系统分析、补丁分析、匹配三部分，简单来说，时间花销与方法的规模是成比例的，ReDeBug是基于token的，VUDDY是基于语法的，MVP是基于语义的，因此所花费的时间也是以此递增。

• Q3：在MVP的匹配过程中，如何配置阈值？

由上图可见，当匹配的漏洞sig大于0.8且补丁sig小于0.2时，MVP可以达到较高的准确率。当匹配的漏洞sig大于0.8时，召回率会大幅下降，而匹配的补丁sig比例不影响召回率（因为其实相当于不考虑补丁sig的话，主要问题是假阳性率，对召回率影响不大）。

• Q4：语句抽象和语句信息的采样对结果的影响有多大？

如上图所示，其含义是Vsyn采样时信息熵阈值的大小对结果的影响。有图可见，该采样的效果还是非常明显的，阈值在5时，准确率和召回率最高。

• Q5：其他漏洞检测方法检测重复漏洞的性能如何？

本文还对比了VulDeepecker和Devign这两种方法，发现MVP的结果远远好于这两种方法，VulDeePecker召回率仅为7.2%，Devign召回率为36.0%。

Limitation

• MVP只专注于重复漏洞
• 使用joern生成代码属性图，只适用于C/C++
• 通过宏来修复的漏洞代码无法进行检测
• 对形式参数、局部变量和字符串进行抽象，无法发现有相似函数调用或相似数据类型的漏洞

Conclusion

本文提出了一个重复漏洞检测模型MVP，该模型通过同时生成漏洞signature和补丁signature的方式来区分漏洞函数是否打过补丁；同时提出了一种新的函数切片方法，只提取与漏洞和补丁相关的语句，在语法和语义级别生成更加精确的漏洞和补丁的signature。方法过程如下：首先对于待检测的目标系统，为系统中的每个目标函数生成signature；接着生成安全补丁数据集中每一个（漏洞，补丁）对对应的漏洞signature和补丁signature；最后将目标系统中的每个目标函数的signature与漏洞和补丁signature进行匹配，如果在待匹配集合中发现了与目标函数signature相匹配的漏洞signature，但不存在相匹配的补丁signature，则认为目标函数存在重复漏洞。该方法以函数为检测粒度，针对C/C++代码。