本文总结来自2018-NDSS的K-Miner论文，主要参考白泽和New_Mai的总结，加上我对K-Miner源码的阅读笔记。

一、论文介绍

1.k-Miner总结

K-Miner是第一个对整个Linux内核进行数值流静态分析的工具，主要挖掘的漏洞类型是Use-After-Return、Memory leaks、Use-After-Free、Double-Free、Double-Lock这五类，我们可以学习该工具所用到的静态分析技术，将静态分析用到辅助Fuzz和漏洞利用中去。

本文针对的是整个linux内核，同样面临着静态分析常见的问题，如路径爆炸、资源消耗激增等问题。本文实现了K-Miner，其采用了过程间的数据流分析（inter-procedural analysis）、大规模的指针分析（scalable pointer analysis）和全局-上下文敏感分析（global, context-sensitive analysis）等技术，基于系统调用的接口对内核源代码进行分割（每次分析一个syscall），从而实现对内核源代码进行静态分析，挖掘代码中的内存损坏漏洞。最后作者使用K-Miner分析发现了2个新的CVE漏洞。

2.静态分析介绍

2.1 图介绍

Figure1-Graph.png

过程间控制流图ICFG（Inter-procedural Control-Flow Graph）：如图b，可用于进行基于路径敏感的分析（path-sensitive analysis）。

指针赋值图PAG（Pointer Assignment Graph）：如图c，可用于进行空值分析。此图可看出存在一条路径，使得变量b被赋值为空，会产生一个对应的空值报告。

数值流图VFG（Value-Flow Graph）：如图d，可用于进行污点分析，可用来跟踪单个的内存对象。

2.2 图分析精确度

Whole-Program —— Inter-procedural Analysis：考虑调用边和返回边 Context-Sensitive：即从哪里调用过来的 Flow-Sensitive：保存整个控制流路径

2.3 数据流分析算法和worklist算法

以Reaching Definitions Analysis为例。

问题定义：给变量v一个定义d（赋值），存在一条路径使得程序点p能够到达q，且在这个过程中不能改变v的赋值。

应用举例：检测未定义的变量，若v可达p且v没有被定义，则为未定义的变量。

抽象表示：设程序有n条赋值语句，用n位向量来表示能reach与不能reach。

2.3.1 公式分析

什么是definition？ D: v = x op y 类似于赋值。

Transfer Function：OUT[B] = gen_B U (IN[B] - kill_B) ——怎么理解，就是基于转换规则而得到。

解释：基本块B的输出 = 块B内的所有变量v的定义（赋值/修改）语句 U （块B的输入 - 程序中其它所有定义了变量v的语句）。本质就是本块与前驱修改变量的语句 作用之和（去掉前驱的重复修改语句）。

Control Flow：IN[B] = U_{p a_predecesso_of_B} Out[P] ——怎么理解，就是基于控制流而得到。

解释：基本块B的输入 = 块B所有前驱块P的输出的并集。注意，所有前驱块意味着只要有一条路径能够到达块B，就是它的前驱，包括条件跳转与无条件跳转。

1-Reaching_Definition.png

2.3.2 算法

目的：输入CFG，计算好每个基本块的kill_B（程序中其它块中定义了变量v的语句）和gen_B（块B内的所有变量v的定义语句），输出每个基本块的IN[B]和OUT[B]。

方法：首先所有基本块的OUT[B]初始化为空。遍历每一个基本块B，按以上两个公式计算块B的IN[B]和OUT[B]，只要这次遍历时有某个块的OUT[B]发生变化，则重新遍历一次（因为程序中有循环存在，只要某块的OUT[B]变了，就意味着后继块的IN[B]变了）。

2-可达性分析算法.png

2.3.3 实例

抽象表示：设程序有n条赋值语句，用n位向量来表示能reach与不能reach。

说明：红色-第1次遍历；蓝色-第2次遍历；绿色-第3次遍历。

结果：3次遍历之后，每个基本块的OUT[B]都不再变化。

3-遍历实例.png

现在，我们可以回想一下，数据流分析的目标是，最后得到了，每个程序点关联一个数据流值（该点所有可能的程序状态的一个抽象表示，也就是这个n位向量）。在这个过程中，我们对个基本块，不断利用基于转换规则的语义（也就是transfer functions，构成基本块的语句集）-OUT[B]、控制流的约束-IN[B]，最终得到一个稳定的安全的近似约束集。

2.3.4 worlist算法

本质：对迭代算法进行优化，采用队列来存储需要处理的基本块，减少大量的冗余的计算。

4-worklist.png

3.k-Miner 设计与实现

Figure2-K-Miner Overview.png

如图是K-Miner的整体架构图，K-Miner是基于LLVM和SVF（过程间静态数值流分析）的静态分析框架，主要包含以下三个工作流程：

（1）K-Miner首先接收两个输入，一个是内核代码，另一个是内核的配置文件，这个配置文件记录了一些内核特性，用来告诉前端解析器，哪些内核模块需要编译，哪些模块不需要编译。编译器根据这两个输入去构建抽象语法树（AST），并把它转化为中间表示语言（IR），作为后续的输入。

（2）把上一步得到的IR作为输入，去遍历所有系统调用，对于每一个系统调用，K-Miner会生成辅助后面分析的数据结构，比如调用图(CG)、控制流图(CFG)、指针分析图（PAG）、数值流图（VFG）等，有了这些结果，就可以对每一个系统调用进行相应的漏洞分析。

（3）对于第二步中的分析结果，如果检测到有内存漏洞，则在这一阶段中产生相应的分析报告，包含相应的内核版本、配置文件、系统调用以及程序执行路径等。

Figure3-K-Miner-Core Analysis.png

整个工具核心的分析流程大概分为四步：

（1）Kernel Memory Context Pre-Analysis: 首先对要分析的内核上下文进行一些预处理，包括初始化内核的上下文信息、跟踪堆分配的信息、建立系统调用的上下文信息。

（2）Per-Syscall Value-Flow Analysis: 然后对内核的每个系统调用做独立的分析。为了获得更加精确的系统调用的上下文，作者通过分析函数调用图确定函数指针的可达性，并结合流敏感的指针分析技术进一步进行约束，最后结合全局内核上下文进行分析，得到较为精简的每一个系统调用的可达函数的集合，从而得到一个更加完整、精确的上下文。

（3）Analysis Sanitizer: 在拿到足够多的上下文信息后，这一步会从漏洞挖掘角度做一个精确的数据流分析，以减少工具的误报。文章以检测dangling pointer为例，结合VFG图、PAG图等信息，寻找某个局部结点（也就是局部变量）存在无效的引用并找到对该结点的引用对象，如果找到这样的引用，就表明它是一个悬空指针漏洞。最后将该漏洞所经过的路径信息和相应的结点等保存下来，以便后续处理。

（4）Reporting Engine:  对上一步输出的漏洞信息进行简单的去重以及格式等处理，输出最后的漏洞报告。

4.实验与分析

作者选择了五个版本的Linux内核代码进行测试，总共测试了300多个系统调用，测试的漏洞类型为DP（Dangling Pointer）、 UAF（Use After Free）和DF（Double Free）。

环境：CPU：Xeon E5-4650、8核处理器、2.4GHz的主频。内存32G。

（1）工具测试时间评估：结果表明，对于分析每一个系统调用，K-Miner平均大约需要25分钟测试时间。

Table1-Experiment-Time.png

（2）工具内存消耗评估：结果表明，对于分析每一个系统调用，K-Miner平均使用内存在8.7G到13.2G之间，最大值达到26G。由于作者采用了对内核进行分割分析的思想，所以最终的内存消耗还是在可接受的范围的。

Table2-Experiment-Memory Used.png

（3）漏洞挖掘结果：结果表明，K-Miner总计发现了29个可能的漏洞，以及539个疑似的警告。根据工具的结果结合人工分析，作者发现了两个真实的漏洞（CVE-2014-3153、CVE-2015-8962）。另外在人工分析中，作者发现大部分结果为工具误报，特别是UAF类型的误报偏高，作者提到有一部分原因是因为检查是否为NULL这种条件分支也会被识别为潜在的UAF。

5.评价

误报较严重，文章中介绍的一系列优化策略没有在实验中体现其优劣；K-Miner每次只分析一个syscall，没有分析除syscall以外的代码，如驱动模块，且忽视了由于多个syscall导致的并发漏洞。

值得学习的是K-Miner的数值流分析算法和漏洞建模策略，还有内核划分的思想。

二、K-Miner源码分析

K-Miner是采用C++实现，看代码的难点就是类太多，继承关系复杂，容易看晕。

1.初始化

K-Miner的一大亮点就是初始化。K-Miner代码的三分之一都在进行初始化。

为什么要初始化？静态分析是以syscall入口开始进行静态分析的，直接跳过了系统启动的boot阶段，所以syscall中出现的全局变量可能没有经过初始化，这样直接进行静态分析会很不准确。

K-Miner是怎么做的呢？我就简单总结一下，首先遍历搜索系统启动阶段中负责初始化的函数——InitCall，再找到InitCall中包含的函数和全局变量，所有InitCall都大致按照优先级进行排序（也即系统启动时的执行顺序）。找Initcall中函数和全局变量的过程进行了两次，第一次遍历的是SVF简单构造的调用图，第二次是采用SVF Andersen指针分析生成更准确的调用图。接着找到待分析的目标Syscall中包含的函数和全局变量（记为globalvars），找到对globalvars进行初始化的InitCall集合（记为Initcall-S），在对应的Syscall开头添加对Initcall-S的调用，这样每次分析目标Syscall时，都会先执行Initcall对全局变量进行初始化。

初始化时还做了其他工作。例如，将alloc/free/lock/unlock这四类函数全部替换为ExternalLinkage的同名同类型函数，以便于后序的数值流分析。

2.漏洞检测

K-Miner使用5个pass来挖掘这5个漏洞。都采用了典型的worklist算法来进行数据流分析和路径遍历。

Pass简介：通常，采用PassManager来管理用户实现的pass，PassManager中的Run()函数会自动按顺序调用doInitialization()、doFinalization()、runOnModule()这3个函数，所以一般用户需要自己实现这3个函数，doInitialization()函数在your_pass中最先执行，一般用于初始化；runOnModule()是主要的分析部分；doFinalization()在分析完成后做收尾工作。

5-pass关系.png

总体流程：UseAfterReturn漏洞采用的是数据流分析，MemLeak、UAF、DoubleFree、DoubleLock漏洞采用的是Source-Sink分析。所以UseAfterReturnChecker Pass是单独实现的，完成数值流分析和漏洞检测的整个过程。而MemLeakChecker、UseAfterFreeChecker、DoubleFreeChecker、DoubleLockChecker Pass都是继承了同一个类SrcSnkAnalysis，首先由SrcSnkAnalysis类进行source-sink分析，具体过程是遍历souce点，以source点为起点正向遍历SVFG稀疏值流图，一直走到sink点，将所有能够到达的sink点保存起来，包括走到这个sink点的正向路径。这个时候source和sink点并不是对应上的，也就是说操作的对象不一定是同一个，再遍历该source点可达的sink集合，反向走，看能不能走到source点，能走到则将路径信息保存到sinkPaths。再由MemLeakChecker、UseAfterFreeChecker、DoubleFreeChecker、DoubleLockChecker Pass对sinkPaths进行漏洞检测，并保存漏洞。

2.1 UseAfterReturn

Figure4-Dangling Pointer.png

漏洞说明：如图4所示，子图a模拟了一个具有指针悬空漏洞的系统调用，在add_x函数中，局部指针变量p被赋值给全局指针变量global_p；在remove_x函数中，把全局指针变量global_p置空，但是在do_foo函数中，我们可以看到，只有在满足特定条件（③）下才执行remove_x函数，因此存在指针悬空的漏洞。

检测UAR漏洞：首先从局部变量（local node）开始前向遍历VFG，如果函数的exit个数大于函数入口个数，即判定有对该local node的引用离开了有效区域。例如，对于local_x结点，add_x一个入口，add_x一个exit，do_foo一个exit，最后发现一条路径使得local_x离开了有效区域：local_x->①->②->③->⑤->⑥。然后反向遍历VFG，找到对该local node的引用，则为悬垂指针。找到一条⑥->⑤->③->②->global_p，即存在一个指针悬空漏洞。此外，由于有了PAG图，在反向查找的时候就可以避免访问不属于当前跟踪的内存对象的边（例如：⑤->④）。最后把该bug所经过的路径信息和相应的节点等保存下来，以便后续处理。

2.2 MemLeak、UseAfterFree、DoubleFree、DoubleLock

6-漏洞建模.png

前面已经提到过，MemLeakChecker、UseAfterFreeChecker、DoubleFreeChecker、DoubleLockChecker Pass只需对sinkPaths进行漏洞检测，并保存漏洞。这4类漏洞的有两个不同点，一是对source点、sink点的定义不同，只要定义好了source和sink点，调用SrcSnkAnalysis类即可得到source点到sink点的路径——sinkPaths；二是对漏洞的建模，以下是漏洞的具体判定条件：

（1）MemLeak

• 遍历sinkPaths，也即所有从指定source点到任意sink点的路径，只要找到1个sink点是解引用（释放）结点，则没有内存泄露漏洞（这个判定有漏报，如果存在一条路径没有释放内存，也会导致内存泄露）。

• 没有遇到释放点，则包含漏洞，调用handleBug(root)，创建NeverFreeBug bug漏洞类，设定leakptr位置（即root结点的所在文件名、所在函数名、所在源码行数、变量名）—sourceLoc、从root结点到syscall开头的路径—apiPath、分析时长—time。

（2）UseAfterFree

• SrcSnkAnalysisContext::sortPaths()：流敏感的SinkPaths，即fsSinkPaths。将 sinkPaths 中的元素按照执行流顺序排列，插入到fsSinkPaths（将NullStoreNode 放 fsSinkPaths 的后面，感觉较低效，判断可达性—AnalysisContext::isReachable需要判断VFG_edges值流路径上，前面每个结点是否相同，判断过程复杂）。

• 遍历 fsSinkPaths 中任意两个元素 item1、item2，若item1为释放点、item2为使用点、且两点的值流路径可达，则为UAF漏洞，item2为 NullStoreNode则无漏洞。（可能存在误报，就算item2为使用点，item1

（3）DoubleFree

• 遍历 fsSinkPaths 中任意两个元素 item1、item2，若item1和item2都是释放点、且两点的值流路径可达，则为Double-Free漏洞，item2为 NullStoreNode则无漏洞。（可能存在误报，就算item2也为释放点，item1和item2之间可能还有清零点）。

• 调用handleBug(root, item1, item2)，创建DoubleFreeBug 漏洞类，设定悬垂指针—souce、释放点—sink1、释放点—sink2的位置（所在的文件名、函数名、行数）、从root结点到syscall开头的路径—apiPath、分析时长—time。

（4）DoubleLock

• 遍历 fsSinkPaths 中任意两个元素 item1、item2，若item1和item2都是加锁点、且两点的值流路径可达、且item2不在 nonCriticalPaths 集合中，则为Double-Lock漏洞；若item2为解锁结点，则无漏洞，进一步若item1和item2可达，则item2可达的所有结点都加入到 nonCriticalPaths。

• 调用handleBug(root, item1, item2)，创建DoubleLockBug 漏洞类，设定锁对象—souce、加锁点—sink1、加锁点—sink2的位置（所在的文件名、函数名、行数）、从root结点到syscall开头的路径—apiPath、分析时长—time。

3. 优化

如何使得检测效率更高？

重访函数：使用不同的pass时，可能会使用不同的输入多次访问同一函数，该函数又会调用其他函数并重复转发结果，效率低下。改进就是，对函数的所有可能上下文仅处理一次并存储中间结果，如果某分析使用给定context来查询某个函数entry node，该分析会先检查是否已访问过该node，重用之前的结果。

并行：使用OpenMP 实现部分的并行。说白了就是简单的使用了OpemMP库函数，把作者认为能够并行的代码框起来，让编译器去自动化并行。

参考：

白泽带你读论文丨K-Miner: Uncovering Memory Corruption in Linux

【读书笔记】ndss2018_K-Miner_ Uncovering Memory Corruption in Linux