彭双和 ，韩 静

(北京交通大学 计算机与信息技术学院，北京 100044)

随着信息化时代的到来，计算机行业蓬勃发展，随之而来的还有层出不穷的软件漏洞，为计算机安全带来很大的隐患，尤其是内存方面的漏洞.据国家信息安全漏洞库的最新统计，大多数高危漏洞都是内存安全漏洞.这些漏洞一旦被不法分子利用，就会产生不可估量的危害.除了目前广泛出现的内存泄漏、悬空指针、未初始化读、use-after-free[1]等漏洞外，还有一些有意或者无意的不当操作引发的低效代码.这些漏洞轻则导致程序运行低效，重则导致系统失效甚至崩溃，从而降低系统可靠性.而且这些内存错误都很难被发现，寻找也相当费时费力，靠一般手段是很难检测到.尤其是内存泄漏，随着计算机内存的不断扩大，程序员对于内存泄漏的感知越来越弱，这就使得内存泄漏不断堆积，最终危害系统安全.

目前对于内存漏洞的检测主要分为静态检测和动态检测[2]两方面.静态检测是在程序不运行的状态下针对源程序进行的一种检测方式，可以确保100%的代码覆盖率.但对于在程序运行过程中才会被触发的漏洞则无能为力，导致较高的误报和漏报.如EXE[3]、KLEE[4-5]采用符号执行的方式检测内存错误，通过计算执行路径中可达分支的路径约束来确定是否激活程序漏洞.但是当源码不可得时，这些方法将无法实现.

动态检测在程序运行过程中进行，最常见的动态检测方式是二进制插桩(Dynamic Binary Instrument，DBI)[6].通过二进制插桩，可以一步一步地对目标二进制进行拆解，从而获取需要的信息.在程序运行过程中检测，可以有效避免静态检测的漏判，实时检测出可执行程序在运行过程中发生的错误，但是动态检测也会带来较大的系统开销.如基于Valgrind[7]开发的Memcheck框架的一个内存错误检测器，它可以检测出大多数的内存错误.Memcheck实现了一个仿真的CPU，被监控程序由这个仿真CPU解释执行，从而有机会在所有内存读写指令发生时，检测地址和读操作的合法性.但该方法的开销较大，而且缺少错误的详细信息.此外，Memcheck只能检测堆中的内存错误，对于大多数内存攻击都无能为力.文献[8]提出了一种智能模糊测试方法来检测内存错误，可以对二进制程序进行检测.但它只能检测基于堆的内存错误，不能检测对于栈中的内存错误.

本文作者提出一种动静相结合的方式，即采用动态插桩获取可执行程序的内存轨迹，然后静态分析轨迹得到检测结果.该方法可以在保证精确度的同时大大缩减系统开销，而且可以在无需程序源码的情况下尽可能完整的还原程序内存访问的轨迹及其函数调用，并以可视化的形式展现出来，清晰直观地描述内存访问的轨迹及内存错误发生的位置和类型.

1 基于内存访问轨迹的脆弱性检测

本文提出的基于内存访问轨迹的程序脆弱性检测方法的总体框架如图1所示，主要分为在线分析和离线分析两个模块，分别负责内存访问轨迹的获取和内存脆弱性的约束求解与检测.

首先根据有限状态机模型[9]定义相关脆弱性，然后对可执行程序进行在线分析，在不影响进程正常执行流程的前提下，可选择性的插入分析代码进行实时分析，获取进程内存访问的轨迹.最后通过相应的脆弱性约束进行离线分析，与处理后的内存轨迹一起通过约束求解器求解，最终得到脆弱性类别及位置.

1.1 脆弱性约束定义

脆弱性即漏洞，是指软件中存在的一些功能性或安全性的逻辑缺陷.本文将可执行程序的内存操作过程看作一个有限状态机，包括堆内存的从内存分配到内存释放过程，以及栈内存的读写过程，建立相应的模型如图2所示.内存访问的轨迹即为有限状态机中各个状态之间的转化，图2实线和点线中箭头所示方向的所有操作都是合法的状态转化过程，缺少某个操作或者操作顺序错误都会导致不同程度的内存脆弱性，基于这些不合法的转化定义以下几种内存脆弱性：内存泄漏、未初始化读、双重释放、use-after-free、死写以及重复频繁读.

将上述有限状态机模型定义为一个五元组

M=(K，∑，f，S，Z)

(1)

式中：K为有限状态的集合；∑为事件集合；f为状态转换函数；S为初始状态；Z为终态集，具体定义如下

K={start，alloc，write，read，free，end}；

∑={alloc(addr)，read(addr)，write(addr)，free(addr)，exit(fun)}；

f的定义见表1，内存执行在不同状态下可以进行不同的操作，而且执行不同操作的安全性也是不同的，表1中包含了部分转换可能导致的脆弱性.

表1 有限状态机的状态转换

其中，内存泄漏是指程序中用户动态分配的内存由于某种原因(程序未释放或无法释放)，造成系统内存的浪费，会导致程序运行速度减慢甚至系统崩溃等严重后果.图2中①就是一种内存泄漏，是由于分配了一块内存空间，却没有对它进行释放导致的.

未初始化读是一种使用未初始化变量导致的内存读写错误，如图2中②，它通常会导致严重的后果，可能使系统崩溃.未初始化读代码片段如下，由于局部变量c在使用前没有初始化，就产生了未初始化读的错误.

char *readline(char *buf){

char c;

char *savebuf=buf;

while(c!=EOF&&(c=getchar())!=′ ′)

*buf++=c;

*buf=′′;

if(c==EOF&&buf==savebuf)

return NULL;

else

return savebuf;

}

死写[10]指的是同一地址处两个有效的写操作之间没有读操作，从而导致第一个写操作无效，如图2中的③操作，或者是对某个地址进行一次写入后直到程序终止都没有读取该位置的值，造成了冗余操作，这样会大大降低了程序的执行效率.同理，分配内存后直接释放而不使用也会导致效率低下，尤其是频繁申请释放会带来较大的性能瓶颈，如图2中的⑧操作.

图2中的④⑤操作将导致use-after-free错误，而⑥会导致double free错误，它们都是悬空指针引起的.将指针定义为一个由指针存储的最低地址和指针指向的地址组成的对，当指针指向的对象被释放时，该指针就成为悬空指针，其指向的地址成为死内存.这里的关注点在于内存访问操作的时间先后性，而不是空间错误.因此，由于错误的指针算法或者缓冲区溢出导致指向预期内存地址之外的指针不认为是悬空指针.CVE数据库中绝大多数use-after-free漏洞和所有双重释放漏洞都是由释放堆内存创建的悬空指针引起的.

对同一地址频繁的读也是一种异常情况，不仅严重影响执行效率，而且最新的一些危害极大的内存漏洞如Spectre[11]、meltdown[12]、rowhammer[13]等都具有这种特征，通过热点分析对比正常应用程序和恶意程序的内存访问模式，发现恶意程序普遍对内存操作频繁，而且这几种漏洞都具有对同一个地址不停读取的特征，因此可以利用这个特征来检测这几种内存漏洞.

本文通过将程序分析的问题转化为约束求解的问题来检测这几种脆弱性.根据上述几种内存脆弱性所违反的转化过程，定义一些脆弱性约束(Vulnerability Constraint，VC)，从而实现对内存访问模式的制约.一旦满足某种约束，就表示程序中存在该类型的脆弱性.为了保证程序执行的时序逻辑，采用一个顺序ID号表示内存操作的执行顺序，ID号越小表示操作越早执行.从而可以将上文提到的几种脆弱性以约束求解器可以理解的符号的形式表示，表2即为具体的脆弱性约束表达式.最后将这些表达式与内存访问轨迹通过约束求解器求解，若有解，则存在脆弱性，从而检测到内存错误发生的位置.

表2 脆弱性约束定义

1.2 基于Intel-Pin的内存轨迹获取

该模块通过动态二进制插桩实现，目前比较流行的DBI框架有Pin[14]、DynamoRIO[15]、Valgrind、Nivana[16]等.其中Pin是Intel公司开发的一个二进制插桩框架，其性能和效率方面都优于其他平台.因此，选用Pin获取进程在运行过程中的内存分配和访问等相关信息.

Pin支持IA-32和x86-64指令集架构，可用于创建动态程序分析工具，然后可以使用这些工具来监视和记录进程运行时的行为.使用Pin创建的名为Pintool的工具可用于在用户空间应用程序上执行程序分析.Pintool对可执行程序的检测是在编译后的二进制文件运行时执行的.因此，在想要分析一个程序但没有该程序的源代码的情况下，Pin尤其有用，这一特征也与本文的目标十分吻合.

通过Pin提供的不同粒度级的插桩以及丰富的API，可以在每条用户态指令执行前和执行后获取该指令的上下文信息，包括进程空间中的内存数据、指令信息、寄存器的值等，并对这些指令进行分析，内存访问轨迹获取的流程如图3所示.其中函数记录通过函数级插桩(Routine instrumentation)实现，内存访问记录通过镜像级插桩(Image instrumentation)获取，而内存分配记录通过指令级插桩(Instruction instrumentation)实现.

内存操作主要包括以下三部分内容：

1)内存分配：内存分配函数是包含在堆中分配的内存空间，以malloc和alloc之类的内存分配函数为例，通过跟踪内存分配函数来获取分配缓冲区的地址和大小.

2)内存释放：内存释放函数与分配函数一一对应，通过跟踪内存释放函数记录堆内存是否释放以及释放的地址.

3)内存访问：内存访问指的是对内存区域的读或写操作，不局限于堆，通过跟踪内存读写操作来获取内存操作的地址.具体流程如下：

①通过指令级插桩函数INS_AddInstrumentFunction检测每条指令的执行信息；

②在回调过程中，如果指令地址不在被测程序的范围内，就不进行检测；

③通过INS_IsMemoryRead函数和INS_IsMemoryWrite函数来检测是否进行了内存读写操作，并用INS_InsertCall函数添加对分析函数的回调；

④当分析函数被调用时，意味着发生了内存操作，此时生成一条内存轨迹.

对于大型二进制文件或者内存操作频繁的程序，如果逐条分析指令并记录轨迹，会导致轨迹爆炸，不便于后续分析.因此本文提出以下3个解决方案进一步对轨迹进行过滤，只保留对后续分析有用的记录：

1)由于所有程序都是以main函数为入口，因此可以通过镜像级插桩函数IMG_IsMainExecutable只跟踪被检测程序的内存操作，而过滤掉一些系统调用等对后续分析没有帮助的信息；

2)通过函数来获取特定的内存轨迹.以某个函数作为输入参数，只获取该函数内部的内存访问操作，即可有效缩减内存轨迹，但此时需要预先知道可执行程序中调用的函数名.可以通过gcc自带的一个性能测试工具GPROF[17]来实现.通过GPROF检测可执行程序，即可生成函数调用图，获取到被测程序中包含的函数列表.然后选择某一个或几个函数名作为参数输入，运行pintool，可以获取到该函数内部的内存访问轨迹.如果想获取全部的轨迹，可以将“*”作为输入，此时pintool将检测全部的内存访问轨迹以及每个函数调用.具体的实现过程如图4所示，而函数的进入和退出事件也是通过插桩函数来判断的，这样就可以实现部分轨迹的追踪.

3)只跟踪特定地址范围的内存轨迹.一般着重检测热点范围内的轨迹，热点即内存访问频繁的地址范围.一般地，访问越频繁的内存空间，其出现脆弱性的可能性也相对越大，因此可以先通过统计每个内存操作的执行次数，判断其是否超过某个设定的阈值，来确定热点区域.然后通过命令行选项来过滤热点内存地址范围，即可获取到指定地址范围内的内存访问.

1.3 约束求解

Z3[18]是来自Microsoft Research的一个SMT(可满足性模理论)[19]求解器，能够检查逻辑表达式的可满足性.

使用Z3求解器求解条件约束，需要通过其自带的一些API接口将表达式中的各个变量、常量转换为其内部使用的数据结构变量.然后根据表达式的内容，调用相应的接口函数.最后通过assert接口将转换后的表达式生成为对应的逻辑表达式，再调用check接口进行求解.最终得到的求解结果为有解、无解和未解出3种情况.

将表2中定义的脆弱性约束和预处理之后的内存访问轨迹混合约束求解，得到脆弱性类别及地址.具体流程如图5所示.

如果在同一地址处存在内存分配函数，不存在释放函数，则存在内存泄漏；如果在同一地址处，已经存在释放函数，再次释放则存在双重释放的漏洞；如果在相同地址处，不存在写操作，直接进行了读操作，则是一个未初始化的读；如果在已经释放内存块之后又进行了读或写操作，则是一个use-after-free漏洞；如果在同一地址处出现两次连续的写操作，而中间没有读操作，则该地址处存在死写；如果一个地址存在重复频繁的读操作且超过了设定的阈值，则很可能存在脆弱性.

根据求解结果，如果满足某个脆弱性约束，则该程序存在该种脆弱性，并将出错地址及类型输出在结果报告中.

2 实验结果及分析

相较于前人的工作，本文增加了可视化的模块，可以直观的看到内存操作的序列以及出错的地址和错误类型.以Linux系统常用的压缩工具bzip2为例，将其作为输入运行本文的检测工具，最终的检测结果报告如下

1 WRITE [0×6156c0] [21] dead_write

2 WRITE [0×615f0c] [29] dead_write

3 WRITE [0×6156d4] [47] dead_write

4 WRITE [0×615f00] [30] dead_write

5 WRITE [0×615ae0] [31] dead_write

6 WRITE [0×615f18] [18] dead_write

其中第1列，第2列表示操作类型及地址，第3列表示执行ID，第4列是错误类型 ，由检测结果可知bzip2具有多处死写的脆弱性，在后续的实验中本文也检测了其他常见应用程序的相关脆弱性.

内存访问轨迹及漏洞报告如图6所示.用不同的形状表示不同的操作类型，加深表示该操作存在脆弱性，其对应的横坐标表明出错的地址.将鼠标悬浮在某个点上时，会显示该点的操作，如果该点存在脆弱性，则会显示脆弱性类型.以ID为21的点为例，其表示一个写操作，横向观察发现，在该地址处已经存在一个写操作，而且这两个写操作之间没有读操作，故该处存在死写.

2.1 结果评估

为了评估结果的有效性，在ubuntu14操作系统上进行实验，并且通过基准测试集程序Juliet_Test_Suite_v1.2_for_C_Cpp[20]检测最终的结果，这是美国国家标准和技术研究所软件保障参考数据集(SARD)[21]，其中包含了一组用C和C++编写的易受攻击的程序，并根据Common Weakness Enumeration(CWE)数据库中的故障和漏洞进行分类.表3显示了对一些程序的测试结果.

表3结果显示本文的方法对于内存泄漏、双重释放、use-after-free以及未初始化的读都具有很好的检测效果，表4是对存在重复频繁读特征的几种高危漏洞的检测结果，通过对比一些正常程序的频繁读取次数，可以看到这几种漏洞都具有明显的重复频繁读取同一个地址的特征，表明可以据此检测出这几种漏洞.

对于死写的检测，为了方便评估，定义

(2)

式中：D为死写率；dn表示发生死写的次数；wn表示总的写入次数.

对常见Linux应用程序进行检测，在SPEC2006[22]上进行测试，结果如图7所示.

表4 重复频繁读检测结果

由图7可见该测试集中大多数程序都存在死写问题，大量冗余写入，也是代码低效的很大一部分原因，检测死写对于提高程序执行效率具有很大意义.在实际生产中，这样的低效代码屡见不鲜，在事先缺乏对程序整体用到的存取指令完全了解的情况下，很容易写一些冗余代码.例如，在申请某个数组的时候会给其赋初始值，但在真正用到时需再次赋值，便会造成无效写.死写虽然不会为程序带来致命后果，却是导致程序低效的原因之一，应该尽量避免.

2.2 性能分析

将本文方法与目前使用的内存脆弱性检测工具Memcheck作对比，Memcheck基于Valgrind框架，而本文方法基于Pin框架，框架本身带来的开销也应作为检测开销的一部分，因此可以选取合适的被测程序直接对比本文方法与Memcheck的检测时间.

由于循环等结构的影响，实际上代码量和内存轨迹之间没有必然联系，因此为了评估其性能，本文选取了一些简短的小程序、上文提到的漏洞库中的程序以及一些较大程序分别进行了检测，得到不同轨迹量的一个大致区间，从而统计了检测时间随内存轨迹量变化，并与Memcheck进行比较，结果如图8所示.

图8结果显示两者的检测时间都随着轨迹量的增长呈指数型增长，由于时间单位为秒，也在可接受范围内，本文的方法在时间开销上明显优于Memcheck.而且在检测常见的内存脆弱性下可以检测一些编程过程中容易出现的代码低效问题，这也是相较于Memcheck的一大优势.

3 结论

1)通过将内存访问转化为有限状态机模型，从而得到与内存访问顺序相关的脆弱性约束，再结合在线分析得到的内存访问轨迹，利用Z3进行混合约束求解，最终得到程序中潜在的或者是已经存在的内存脆弱性，并标明其出错地址.同时,对于导致代码低效的操作也进行了检测，在提高代码效率方面起到了积极作用,对于一些恶意程序起到一定的预警作用.

2)本文的检测过程不影响被测程序的执行，这也是保证检测正确的一个重要因素，可以在缺乏源代码的情况下进行漏洞分析.通过实验验证，本文提出的方法可以快速精确的定位内存脆弱性，检测结果也更加直观清晰，可用性更高.

下一步工作将考虑结合循环检测对漏洞严重程度进行定级，使得检测更加精确.