基于图的漏洞定位

分享一篇来自USENIXSE' 23的论文，题目为："VulChecker: Graph-based Vulnerability Localization in Source Code"。文章的代码和数据已开源：https://github.com/ymirsky/VulChecker。

在软件生命周期的最早阶段检测软件漏洞至关重要，这主要是因为攻击者可以利用已部署软件中的漏洞来实现各种恶意目的。而在软件生命周期的各个阶段修补漏洞的成本会大幅增加，如：修补在已部署软件中发现的漏洞的成本比在实施过程中修补漏洞的成本高得多。因此，几十年来，检测软件源代码中的漏洞一直是学术和商业研究与开发的一个高度活跃的领域。

作者提到，现有SAST（Static Application Security Testing）工具的一个问题在于难以检测复杂的上下文漏洞，因此导致较高的误报率。对于基于学习的漏洞检测方法而言，（1）这些方法对整个函数或代码区域进行预测，（2）无法对发现的漏洞类型进行分类。这导致开发人员在使用这些方法时，需要在没有辅助信息的情况下，从数百行代码中搜索漏洞（也就是检测粒度太大）。对于没有对漏洞进行分类的工具来说，这甚至更成问题，因为开发人员不知道他们在寻找什么或需要什么补救方法。加之现有机器学习技术中经常出现假阳性的情况下，这个问题会被放大。

为此，作者分析了现有方法存在的问题，并得到如下Insights：

• 广泛的程序切片。为了定位漏洞，当前的方法是从中取一个子图作为预测时观测的对象。要么是一个完整的函数，要么是从中提取的以兴趣点（PoI，points of interest）为中心的连续区域（也称为程序切片）。因此，对的预测可能涉及数百行代码。这也使优化器更加困难，因为可能包含许多潜在的根本原因和表现点。Insight 1：为了提高预测的精确度，观察对象必须与漏洞的位置直接相关。

• 不完整的代码表示。为了将转换为机器学习可以理解的格式，作为预处理步骤，从AST或函数派生的符号（比如：代码语句）要么被压缩、要么使用word2vec等方法嵌入。这种表示软件的方法与机器学习技术兼容，但不是最理想的，因为它阻止分类器直接推理指令和依赖语义。此外，来自AST的信息要么（1）被忽略、（2）以抑制基于图的学习的方式被包含，要么（3）以损害代码语义和模型效果的方式被不正确地包含。Insight 2：为了在这项任务中实现有效的基于图的学习，需要一种新的代码表示，它可以正确地合并AST信息流。此外，应该在中明确提供指令级语义，以实现高效和有效的学习。

• 表现距离。漏洞的表现可能在其根源之后数百行才出现。目前的GNN方法使用的模型只能将节点信息传播一两步远。因此，这些GNN模型无法推断潜在的根本原因是否直接影响潜在的表现点。相反，这些模型仅限于识别任一点周围的局部模式（例如，memcpy之前缺失的保护分支）。Insight 3：为了提高模型识别漏洞的能力，模型必须能够识别整个的因果关系。

• 缺少有标签数据。深度学习需要数千个样本进行训练。然而，由于在指令甚至行级别打标签既困难又昂贵，所以不存在大型细粒度数据集。因此，当前的工作要么:（1）使用合成数据集（如：NIST SARD），它不能推广到大型项目或真实世界的代码，要么（2）使用仅标记代码区域（程序片段）或整个函数的数据集。Insight 4：为了在源代码中实现经济高效的高精度检测，需要开发数据增强技术来有效扩展现有数据集。

• 程序表示级别。源代码级编程语言是为程序员的易用性和灵活性而设计的，因此可以在一行源代码中捕获几个相互关联的高级操作。这种丰富的指令语义与软件漏洞的特征形成鲜明对比，软件漏洞通常与原子和机器级指令语义相关联。大多数先前的工作是从源代码中提取，而不降低或编译它（也就是说所表达的是高级语言的语义，而非机器码级别的语义）。因此，这些模型面临着从抽象程序表示中识别低级漏洞的挑战。Insight 5：为了提高模型对具有原子机器级特征的漏洞的推理能力，应该捕获低级别的指令语义。

这篇论文的Related Work写法很值得学习。

VulChecker的框图如图2所示。

• ePDG生成

ePDGs的节点表示原子机器级指令，边表示指令之间的控制和数据流依赖关系。

（1）使用低级别的LLVM表示代码

ePDG生成的第一步是将源代码编译成LLVM IR，它提供了目标程序的机器级表示。该过程极大地简化了关于控制流（例如，源代码中复杂的分支结构被简化为测试单个条件的条件转移）、数据流（例如，定义使用链更短且更简单，因为它们基于虚拟寄存器值而不是源代码变量）和程序语义（IR指令是原子的并且可直接转换为指令集架构操作码）的程序表示。为了执行源代码的降级，VulChecker使用LLVM的C/C++前端Clang。在降级过程中，VulChecker指示Clang在IR中嵌入调试信息，这使得IR指令可以追溯到源代码指令。如果包含标签，则使用LLVM提供的调试信息将它们传播到LLVM IR。如果源代码包含label，则使用LLVM提供的调试信息将它们传播到LLVM IR。这些label在稍后阶段被传递给ePDG节点。

除了简化程序表示外，VulChecker还使用LLVM提供的保留语义的编译器优化来简化和更好地表达中的代码。具体来说，它应用了:（1）函数内联，以被调用函数体的具体副本替换IR中的函数调用位置;（2）间接分支扩展，以消除间接分支结构;（3）死代码消除，以减小输出图的大小。总之，这些优化确保VulChecker可以在原始程序的作用域中高效地分析ePDG过程间信息，因为ePDG在最小尺寸的连通图中包含完全精确的控制和数据流信息。

（2）构建ePDG

ePDG可以表示为，其中表示节点（指令）集合，表示边（流）集合，和都是节点和边到类和属性的映射。具体来说，是节点到一类指令的映射，即：，其中是LLVM指令API中所有类型的指令集，是类型的所有可能的属性集。是边到节点对的映射，即：，其中表示数据类型为控制流/数据流的一类边，表示类边的属性，如：数据依赖类型。

VulChecker使用LLVM的中端优化器Opt的自定义插件来生成。该插件首先调用 LLVM 的内置控制流和数据流分析，对目标代码进行逐指令扫描。对于每个指令 ，VulChecker创建一个相应的节点和映射。接下来，VulChecker使用LLVM的API提取关于的语义信息，以填充的条目（例如，operation或者该指令是否是条件分支等）。除了直接从LLVM的API获取的语义信息之外，这些属性还包括调试信息（例如，源文件和行号），指示潜在根本原因和表现点的tag，以及用于模型训练的实际根本原因和表现点的label。

接下来，VulChecker执行第二次逐指令传递，以在中生成控制流和数据流边。这是使用LLVM的API确定的，该API用于识别指令的前置指令/后续指令以及定义/使用的值。对于每个给定指令的前趋和后趋，生成具有适当类型和属性的对应的边。控制流边被分配void数据类型，数据流边被分配与原始节点（）中的值定义相对应的数据类型。在对源代码生成的IR指令进行两次遍历后，ePDG就构建完成了。VulChecker以JSON格式输出，供下一步的采样使用。

• 采样

首先，识别中的PoI，它们都是给定CWE（表示为）的潜在表现点。然后，VulChecker从中切割子图，使锚定在中作为终止节点。

（1）PoI选择标准

为了从中提取样本，首先需要确定中给定CWE可以自我表现的节点。作者使用潜在显现IR指令的查找列表来识别一个PoI，即：。该列表是基于领域专业知识和相关工作进行筛选的。具体来说，对于整数溢出（CWE-190），PoI是对传递整数参数的函数的任何调用。这是一种启发式方法，在之前的工作[1]中已得到充分验证。对于栈和堆溢出（CWE-121，122），PoI分别是本地或动态分配内存的任何存储指令。对于释放后使用（CWE-416），PoI是对动态分配的内存的任何内存访问；对于双释放（CWE-415），是对内存管理器的释放函数的任何调用。

（2）程序切片

使用广度优先搜索算法（BFS）从开始向后对进行遍历，直到达到预定深度。所得到的子图有效地捕获了可能导致的正面或负面表现的任何保护分支和根本原因。因为BFS不加区别地在控制流和数据流边上执行。因此，就控制流而言，可能相距甚远的指令（即：中间基本块）可以通过数据流紧密联系在一起。

（3）Labeling

对于每一个，根据其是否是易受攻击的来为其分配标签。其中，正标签（易受攻击的）被分配到源代码的行，然后使用debug符号映射到IR。如果一行源代码包含一个以上的潜在表现点，则将标签应用于语句中最后一条相关的IR指令。而任何未被标记为易受攻击的都被标记为负标签。

• 特征提取

对于每个，制作一个机器学习观测对象，它具有与相同的图结构。的节点和边被分配表示相应指令和流的特征向量。表2总结了这些特征向量，其中Count字段是特征的数量。总共有1352个节点特征和8个边特征。节点的特征向量使用操作、结构和语义特征来捕获相应的指令。边特征则捕获关于连通性（控制和数据流）的信息。

Operational节点特征。为了捕获在节点（指令）上执行的操作，作者提取静态值、操作类型、基本功能以及指令是否是if子句的一部分等特征。静态值对于识别由开发人员实现的安全检查非常重要。了解一条指令是否是if子句的一部分也有助于识别错误预防检查或可能出现错误的罕见情况。操作和功能特征是代表节点（指令）动作的one-hot编码。这些特征的类别是通过扫描几个大型软件项目（超过4000万个节点）收集的，操作包括：add，load，store，allocate，unsigned_divide，logical_shift_right，get_element_pointer等；其中一些函数包括：malloc，free，fmemopen，printflseek等。同时，作者还为没有出现在代码集中但可能出现在训练和测试中的操作定义为other，以便网络可以对这些事件进行加权。为了鼓励模型学习模式并避免偏见（作弊），作者将的函数特征设置为零。由于VulChecker在ePDG降级过程中内嵌所有用户函数并使用IR表示，因此不需要像以前的工作那样标记函数名。因此，的特征明确表达了对学习过程最有益的信息。

Structural节点特征。由于是一个有向图，作者使用图的特征来帮助模型理解每个节点在结构中传播消息时的影响。例如，知道从最近的潜在根本原因点到锚定的潜在表现点的距离，为机器学习模型提供了有关相关节点在图中位置的隐含信息。使用领域专业知识确定中的潜在根本原因点。如，整数算术运算是整数溢出、堆栈和堆溢出的堆栈和堆写入以及释放内存以供释放后使用和双重释放的潜在根本原因。同时，还使用中间中心性度量（BEC）特征[2]来衡量节点对于在中高效绘制节点间路径的重要性的分数。这是基于图的机器学习和基于图的异常检测中常用的特征。作者使用此功能是因为它为本文所提出的S2V模型提供了关于节点在中的相对位置的隐式信息。

Semantic节点特征。除了标记到最近的根本原因点的距离之外，作者还指示节点本身是否是潜在的根本原因或表现点。这有助于模型定位潜在的漏洞源以传播到和其他可能在之前吸收信号的表现点。

边特征。对于边特征向量，指出边的类型（控制流或数据依赖性）并捕获数据依赖性的数据类型，以便模型可以捕获哪种数据去哪里。通过了解静态值流、外部输入（来自某些函数）及其数据类型，模型拥有足够的信息来预见数据对程序的影响。

，其中是节点特征矩阵，是边特征矩阵，为 的邻接矩阵，是它的入射矩阵。我理解其实就是对的向量化表示。

• 模型学习

VulChecker的网络由两个部分组成：图嵌入网络和深度学习网络。其中，基于Structure2Vec（S2V）[3]，通过在图的结构中传递消息来生成节点嵌入。

本文中，作者对每一个目标CWE训练一个模型。

• 数据增强

要创建一个可以在真实项目中运行的模型，必须在反映真实世界的样本上进行训练，这些样本具有大量不相关的代码以及根本原因和表现点之间的良性模式。现有的一些行标签数据集，如NIST的Juliet C/C++测试套件，它们由不反映真实世界代码的简短合成程序组成。在缺乏真实的行标签数据集的情况下，作者提出了一种数据增强技术，该技术将来自合成行标签数据集的漏洞与真实世界的代码相结合，以生成真实的训练样本。

为了实现这一目标，作者通过拼接多个包含漏洞的Juliet ePDG子图，从GitHub的真实项目中扩充了一个干净的的ePDG。这将生成一个具有许多正面表现点的训练样本，每个点都是在程序切片期间单独提取的。伪代码如下：

给定一个现实世界项目的ePDG和一组从从Juliet数据集提取的漏洞子图。通过如图3所示的方式增强。

在数据增强过程中，需要（1）保持漏洞的数据流和静态可达性属性，以及（2）拼接ePDGs不会使插入的漏洞无效。

下面是一些实验结果。

参考文献

[1] Wang T, Song C, Lee W. Diagnosis and emergency patch generation for integer overflow exploits[C]//Detection of Intrusions and Malware, and Vulnerability Assessment: 11th International Conference, DIMVA 2014, Egham, UK, July 10-11, 2014. Proceedings 11. Springer International Publishing, 2014: 255-275.

[2] White D R, Borgatti S P. Betweenness centrality measures for directed graphs[J]. Social networks, 1994, 16(4): 335-346.

[3] Dai H, Dai B, Song L. Discriminative embeddings of latent variable models for structured data[C]//International conference on machine learning. PMLR, 2016: 2702-2711.