Automatic Inference of Search Patterns for Taint-Style Vulnerabilities

出处：2015 IEEE Symposium on Security and Privacy (网络与信息安全A类)

作者：Fabian Yamaguchi, Alwin Maier, Hugo Gascon, and Konrad Rieck University of Gottingen, Germany

1. 概述

1.1 摘要

提出了一种自动推断C代码中污染型漏洞的搜索模式的方法。给定一个安全敏感的槽，例如内存函数，方法自动识别相应的源-槽系统，并构造模式来建模这些系统中的数据流和消毒。推断的模式表示为代码属性图中的遍历，并能够有效地搜索未消毒的数据流-跨越几个函数或特定于项目的API。我们在5个开源项目的不同实验中证明了这种方法的有效性。推断的搜索模式将检查查找已知漏洞的代码量减少了94.9%，并使我们能够发现8个以前未知的漏洞。

1.2 背景

1.2.1 Taint-Style Vulnerabilities

污染型漏洞这个词产生于污点分析中。污点分析是一种在程序中追踪数据传播的技术。污点分析的目标是识别出从攻击者控制的源未经消毒(输入检查)就流向安全敏感的槽的数据流。这个过程需要三个定义：

合适的源(变量定义赋值)
相关的槽(敏感函数)
输入检查规则(消毒)

污染型漏洞可以包括：缓冲区溢出，SQL注入，命令行注入，缺少授权检验漏洞

CVE-2014-0160 心脏滴血

函数后面的memcpy(bp, pl, payload);填充payload长度的pl数据，而payload完全由用户控制，当传入过大数值时，可能导致越界访问pl之后的数据，若将读取的数据返回给用户即可造成敏感信息泄露。在一些测试用例中我们会发现response的length长度值总是比request的长度多出来了19个byte。读源代码可以知道，这是因为TLS和DTLS在处理心跳请求包逻辑中从堆空间上申请的内存大小由type、length、request的数据长度和pad四个部分组成，其中type,length,pad字段分为占1byte，2byte，16byte，所以response的数据总是比request的多出来19byte。

1.2.2 Code Property Graphs

程序结构、控制流、数据流的联合表示。编程模式能够被编码为对图形数据库的查询，从而可以为危险编程模式的实例挖掘大量代码，从而缩小漏洞。

2.创新点

对代码属性图的扩展：增加了语句优先级信息，并且使得利用图数据库查询进行过程间分析成为可能。
对调用模式的抽取：提出了一种新颖的构建调用模式的方法，方法利用聚类算法，并用到了参数的定义和它们的输入检查。
对于模式的自动推断：本文阐述了调用模式是怎样被转换为图遍历形式的调用模式的。

3. 方法

3.1 代码属性图的扩展

在函数调用点的实参和被调用函数的行参之间添加边，以及在调用点和被调用函数返回语句间添加边。扩展到用于过程间分析的代码属性图。

3.1.1 Post-Dominator Trees

与控制流图和程序依赖图一样，每个语句在支配图中都表示为一个结点。这些结点被表示“支配”的边相连。这里支配的定义是：在一个控制流图中，一个结点d支配另一个结点n，当每条经过结点n的路径都需经过结点d。为了把每个结点与它的直接支配相连，我们获得了一个支配树。类似地，一个结点p后序支配一个结点n，当每个通过n的结点都需要通过p。为了把每个结点与它的后序支配相连，我们获得了一个后序支配树。

示例代码：

它的后序支配树如下图所示：

3.1.2 Detecting Argument Modification

反向查找 (没有源码的函数，以函数参数为根，后支配树向下查找对应的调用)

检测参数定义的启发式方法，确定语句是否总是在另一个语句之前执行的能力是至关重要的

后序支配树建立起来之后，我们可以将它应用在检测导致参数变化的函数调用上——这在编译器设计上被称为定义参数(defining arguments)。找到输入源对于一般的库函数，我们可以用标注来进行处理，而内部API并不会被认作输入源。为解决这一问题，我们进行以下处理：对于每个遇到的没有源码的函数，我们通过以下来判断它有没有定义它的参数。

检查是否有未经输入检查的局部变量声明（例如赋值或对构造函数的调用）到达了参数
检查在此函数到它后序支配树中的变量声明的路径中不含其他与该局部变量声明在数据流上直接相连的语句

计算此函数所有调用点中满足以上两个条件的调用点所占比例，如果超过一个阈值则认为它定义了它的参数。我们将此阈值设定为10%。根据这种简单的启发，我们可以重新计算代码属性图中无源码函数的调用点。

解决：内部API，如“heartbleed”漏洞中存在的N2S宏，不被识别为输入源。

图3展示了我们的启发式：局部变量z在第2行声明，没有明显的初始化。然后，在第3行和第5行中，它分别作为参数传递给boo和foo。而对于函数boo，它是合理的假设它初始化z，这对函数foo是不正确的，因为它被调用后的boo可能已经初始化了z。

3.1.3 Propagation of Data-Flow Information

正向搜索 (有源码的函数，沿着调用链查找参数修改)

除了通过库函数检测参数定义的问题外，参数定义可能间接发生，即函数调用的任何函数都可能负责参数定义。

为了考虑到间接的参数定义，我们可以利用调用链来传播数据流信息：检查每个有源码的函数，如果它的参数在函数内部被定义了，并且定义通过控制流到达了出口，那么认为它的参数被定义了。为了确保函数参数定义被准确识别，我们递归地检查函数中的函数调用，如下面算法所示。

分析函数的所有Callees，并将上一节中提出的启发式方法应用于库函数。得到过程间代码属性图。

3.2 推断漏洞的搜索模式

从一个敏感的槽开始，例如内存函数memcpy，我们的目的是生成图遍历形式的搜索模式，从而能够发现数据流到敏感槽中的漏洞。这些模式需要具有一般性，并且它们需要精确地抓住跨函数的数据流。最后，生成的模式需要易于理解并且可修改。
为达到以上要求，我们分四步来生成搜索模式：

从选择的槽(foo)开始，方法自动构造捕获数据流中的源(get())和消毒(b>1)模式。

3.2.1 Generation of Definition Graphs

源代码包含如何定义和消毒它们的参数的信息，但这些信息通常分布在几个不同的函数中，并隐藏在不相关的代码中。为了有效发掘参数是如何定义以及检查的，我们需要一个源-槽的表达，这种表达只包含参数的定义和输入检查，而忽略其他所有语句。为解决此问题，我们为每个源-槽系统生成了一个图表达，称为定义图，编码所有观察到的参数定义组合及其相应的消毒。
要构建定义图，首先局部地为单个函数建模，然后将相关的图结合起来，对函数交互进行建模。

局部函数建模

按照以下规则遍历代码属性图，得到图表达：

对于选定的槽，我们沿着语法树的边到达它的参数。(foo扩展达到参数x、y、z)
对上步得到的参数，我们沿着与之相连的数据流和控制依赖找到定义语句以及控制调用点的条件。(发现定义int z、y < 10)
最后，我们利用过程间的边，从所有定义了我们参数的函数调用走向相应的函数体，在那里进一步识别出影响了我们选定的槽的定义语句。(发现对boo的调用，引导得到*z = get())

我们将所有与槽参数定义相关的函数也视作槽，递归地应用上面的三个规则，获得一个树。

对于以这种方式到达的每个参数，我们将所有各自的调用函数视为槽，并递归地应用这些规则为通过数据流连接到初始接收器的每个函数获得一棵树。这些树可以很容易地从代码属性图中使用深度优先遍历根据给出的三个规则构造。

定义图

这样一个树并不能处理槽所在函数的传入参数。通过建模整个函数的相互作用而不是参数，来将参数联系在一起。
定义图的定义：调用点c的定义图G=(V, E)是一个图，图中V包括局部模拟c，以及c的直接和间接调用者所在函数的树。对于每一个属于V的a, b，如果a表示的函数调用了b表示的函数，那么存在边属于E从a指向b。

3.2.2 Decompression and Clustering

给出任意一个定义图的集合，例如对memcpy函数的所有调用点的定义图集合，我们要从中识别出反映普遍参数定义的组合模式。为此我们利用机器学习的方法为定义图生成聚类。有如下步骤：
定义图解压缩

以上算法给出了获得定义图中所有参数的组合的算法(枚举{int z, a = get(), b = 1}、{int z, a = 1, b = get()})。定义图中每个结点代表一棵树，其中r(V)是定义图的根结点，[v0]代表一个只包含结点v0的列表，符号+代表向列表中添加元素。
聚类被调函数和类型

利用complete-linkage clustering对被调函数和类型进行聚类，使用Jaro距离来进行聚类，通过实验将参数固定为0.8。获得每个参数调用方和类型集群的集合C。

聚类定义图中的组合
我们将被调函数和参数类型的聚类组成一个词袋，将定义图的每一个组合利用词袋模型映射为一个向量，每一维代表被调函数和参数类型中的一类。对这个向量集合进行linkage聚类，利用曼哈顿距离，参数固定为3。

获得参数定义的类似组合集群。

较大的集群表示由许多单独调用支持的强模式，而较小的集群表示不太清晰的模式，仅由少数调用支持。

3.2.3 Creation of Sanitization Rule Overlays

检查规则(条件)：b > 1

将之前抽取的每一个条件表示成为一个语法树，然后将每棵语法树映射为一个向量，进行hash映射(如下图公式)，利用linkage clustering对此向量进行聚类(得到检查规则的条件集合)。

we employ an explicit tree embedding based on the neighborhood hash kernel

3.2.4 Generation of Graph Traversals

我们为基于模式的分析平台Joern构造了一个通用模板，它可以捕获缺少的参数消毒，并且可以很容易地实例化来表达对缺陷类型的不同搜索模式。并使用查询语言Gremlin进行的模板遍历。

生成图遍历模板

我们定义敏感槽的名字，对每个参数数据源的描述，以及对输入处理的描述。它们对应于argiSource 和 argiSanitizer，其中i代表参数的序号。遍历通过对所有的sink的调用点进行，然后利用taintedArgs 和 unchecked 分别遍历每个sink。如下图所示：

其中 taintedArgs 用来寻找sink是否符合source的描述(argiSource)。为达到此要求，首先生成相应的定义图。然后并不对图进行解压缩，而是确定调用点是否能够满足参数描述，这通过查看对每个参数描述，在定义图中是否至少存在一个匹配的语句来进行。

这一步大大减少了需要分析的调用点数量。然而我们还不能知道调用点是否匹配参数描述。为达到此目的，我们解压缩定义图，由此就能够得知参数定义是否匹配了。最后，我们返回所有与描述匹配的定义组合，将它们传递到unchecked。

unchecked代表所有的根据输入检查描述至少存在一个未经检查参数的调用点。通过将定义图中的每个条件与输入检查描述(消毒)进行检查来完成。

模板实例化

为了对模式进行检查，我们通过将参数定义和条件定义分别翻译为参数描述和输入处理描述来进行。对于每个参数，一个数据源和条件的集合是可以得到的，这些仅仅需要被总结为一个容易被专家分析的形式。我们通过确定签名生成中通常执行的最长公共子序列，从这些集群生成正则表达式。使用生成的图遍历可以用来挖掘代码中的bug，也可以让分析人员改进代码。

4. 实验验证

4.1 验证

利用5个开源应用的已知漏洞来评估我们的方法。

• CVE-2013-4513 (Linux). An attacker-controlled variable named count of type size_t is passed as a third argument to the sink copy_from_user without being sanitized, thereby triggering a buffer overflow.

• CVE-2014-0160 (OpenSSL “Heartbleed’). The variable payload of type unsigned int as defined by the source n2s is passed as a third argument to memcpy without being checked, causing a buffer overread.

• CVE-2013-6482 (Pidgin). The string unread is read from the attacker-controlled source xmlnode_get_data and passed to the sink atoi without undergoing sanitization, thereby possibly causing a NULL pointer to be dereferenced.

• CVE-2012-3377 (VLC). The length of the data buffer p_stream->p_headers is dependent on an attackercontrolled allocation via the function realloc and reaches a call to memcpy without verifying the available buffer size, leading to a buffer overflow.

• CVE-2013-4473 (Poppler). The attacker-controlled string destFileName is copied into the local stack buffer pathName of type char [1024] using the function sprintf without checking its length, leading to a stack-based buffer overflow.

表中列出了对于上述漏洞是否找到了正确的源和正确的输入检查，生成的模式个数，生成模式的时间，执行模式挖掘所用的时间，以及减少对调用点人工检查的比例。

4.2 HeartBleed漏洞

我们利用我们的方法在 OpenSSL 1.1.0f 版本中为槽memcpy生成了pattern并进行了漏洞挖掘，过程如下。

对程序中几个库函数进行检查，得出它们被定义(可控)的参数如下表。

找到与memcpy对应的源如下表。

对这些源进行检查，发现n2s是受攻击者控制的源，然后执行如下图所示的模式。

可以看出，我们生成的输入检查规则很容易被安全专家修改。按此模式遍历整个工程，从738个调用点中返回了7个，如下图所示。人工审查后发现了两个heartbleed漏洞如阴影所示。

5. Joern使用

importCode(inputPath="./Test", projectName="test-zp")    创建项目
cpg.method.name("get").callIn.code.l    获取get()方法地址
cpg.method.name("get").callIn.dump    查找发生的上下文
cpg.metaData.l    元数据
cpg.method.name.l    方法名