软件学报  2017, Vol. 28 Issue (9): 2388-2401   PDF    
基于执行踪迹离线索引的污点分析方法研究
马金鑫1, 李舟军2, 张涛1, 沈东2, 章张锴2     
1. 中国信息安全测评中心, 北京 100085;
2. 北京航空航天大学 计算机学院, 北京 100191
摘要: 针对二进制代码的污点分析方法在软件逆向工程、漏洞分析及恶意代码检测等方面具有重大的意义.目前,大多数污点分析方法不支持浮点指令,执行效率较低,且传播的精度也不够高.提出并实现了一种基于执行踪迹离线索引的污点分析方法,以字节为粒度,且支持污点标签.提出执行踪迹离线索引的生成及查询算法,通过离线索引可跳过与污点数据无关的指令,提高污点分析的效率.首次描述并解决了即时翻译执行导致的污点丢失问题.使用污点标签以标识污点的来源和位置.提出较完善的污点传播算法,支持浮点指令,以尽可能精确地刻画污点信息从源操作数传递到目的操作数的过程.实现了灵活的可配置机制,用户可通过黑名单动态地引入污点数据.将提出的方法应用到漏洞检测的场景中,使用12个真实的软件漏洞作为测试样本集,将该方法与TEMU作对比实验,实验结果表明:该方法具备较强的漏洞检测能力,可验证的漏洞数比TEMU更多,且其平均执行效率比TEMU高5倍.
关键词: 污点分析     离线索引     指令踪迹     漏洞检测    
Taint Analysis Method Based on Offline Indices of Instruction Trace
MA Jin-Xin1, LI Zhou-Jun2, ZHANG Tao1, SHEN Dong2, ZHANG Zhang-Kai2     
1. China Information Technology Security Evaluation Center, Beijing 100085, China;
2. School of Computer Science & Engineering, Beihang University, Beijing 100191, China
Foundation item: National Natural Science Foundation of China (61502536); National High Technology Research and Development Program of China (863) (2015AA016004)
Abstract: Taint analysis method in binary code plays an important role in reverse engineering, malicious code detecting and vulnerabilities analysis. Currently, most of taint analysis methods fail to operate float point instruction, and they do not propagate taints accurately and efficiently enough. In the paper, a taint analysis method is implemented based on offline indices of instruction trace, which are byte-grained and utilize taint tags. A generation and query algorithm of offline indices is also presented. Instructions unrelated to taint data are skipped with offline indices, which improves the efficiency of taint analysis. The taint loss problem resulted from real time translation is described and solved for the first time. Taint tags are utilized to denote where the taint data is derived. A more complete taint propagation algorithm, which could operate float point instructions and insure the taint data flow from source operands into the destination operands precisely, is also presented. Flexible user-configuration mechanism is implemented to produce taint data on the fly with black list. The proposed method is applied in vulnerabilities detecting and evaluated with 12 vulnerabilities as test cases. The experimental result shows that this taint analysis method is able to detect more vulnerabilities than TEMU, and is 5 times faster in average.
Key words: taint analysis     offline indices     instruction trace     vulnerabilities detecting    

在面向二进制代码的漏洞检测领域, 污点分析方法一直是研究热点之一.与符号执行等高级分析方法相比, 污点分析方法只需跟踪数据流, 而无需模拟程序的执行, 其运行效率更高, 灵活性也较强.污点分析方法分为静态和动态两种形式.对于二进制代码而言, 因存在难以确定间接引用、间接跳转以及外部输入等问题, 故静态的污点分析方法分析精度较低, 实现难度较大.

而动态的污点分析方法需监控程序的实际执行, 并根据指令的执行踪迹(trace)及其上下文等信息来进行污点传播[1].为此, 本文提出并实现了一种基于执行踪迹离线索引的动态污点分析方法.在真实的软件漏洞测试样本集上的实验结果表明:本文方法具备较强的漏洞检测能力, 可验证的漏洞数比TEMU更多, 其平均执行效率比TEMU高5倍.

本文所提出的动态污点分析方法支持所有Intel X86指令, 包括浮点指令和SSE指令集, 使用标签集合来标记污点来源, 而传统的大多数污点传播方法都是通过单纯的置位来表示污点.作为对传统污点分析方法的一种改进版本, 本文的主要贡献包括如下3个方面:

1)   使用了执行踪迹离线索引技术, 可跳过与污点数据无关的指令, 极大地提高了污点分析的效率;

2)   设计了较灵活的用户配置机制, 可动态地在某个程序点自定义地进行污点的引入或消除;

3)   解决了JIT(just in time)翻译执行导致的污点丢失问题.

1 方法概述

污点分析方法主要包括3大部分:污点引入、污点传播和污点消除.

●  污点引入是指标识需要跟踪的污点数据, 污点数据一般来自于外部输入源.一般可通过两种方式来确定污点数据来源:一种是通过劫持某些系统函数的方式, 如劫持读文件的函数调用, 获取文件被读入内存后的地址, 把该内存块作为污点引入, 常见的可引入污点的系统函数分为文件类、网络类、注册表类; 另一种污点引入的方式是在程序执行过程中由用户自定义引入污点, 当程序执行到某个函数时, 用户根据特殊需求添加相应的污点;

●  污点传播是指在程序执行过程中分析程序的语义, 并根据数据流分析算法将对应的污点从源操作数传播到目的操作数.污点传播算法直接影响整个污点传播流程是否正确, 一般来说, 需要考虑3种类型操作的传播方式:(1) 数据复制操作, 直接将源操作数复制到目的操作数, 如MOV, PUSH, POP操作等;(2) 数据运算操作和位操作, 使用源操作数与目的操作数进行计算, 然后再存入到目的操作数中, 如ADD, SUB, AND, SHL操作等; (3) 副作用, 部分操作可能会引起隐式的副作用, 副作用也必须考虑在内, 如REP操作会影响ECX寄存器、运算操作会影响EFLAGS寄存器等;

●  污点消除是指在污点传播过程中需考虑污点消除的情况, 否则, 污点将无限制扩散.如果源操作数是污点, 而目的操作数是恒定的, 则需要消除污点.假定src为污点, 当遇到“dest=src^src”类的异或表达式时, 需要清除dest的污点标记.

本文提出的动态污点分析方法直接运作在汇编指令上, 支持浮点指令, 支持SSE指令集, 并且分析了所有汇编指令的副作用.使用以字节为粒度的污点传播算法, 即, 每个字节都是独立的污点元, 分析了整个汇编指令集的语义, 为不同类型的指令实现对应的污点传播规则, 并且用不同的标签来标记不同类型的污点, 以区分污点来源.每个污点元都含有一个标签集合, 用来表示该字节是由哪些污点源派生而来.

污点传播粒度的选择比较重要:如果粒度太大, 容易造成污点数据的丢失和不精确; 反之, 则容易引起污点扩散太广, 且相应的污点传播算法也不易实现.在汇编指令中, 大部分指令都是以字节为单位进行计算的, 因此, 本文选取以字节级别为粒度.

污点元的属性是一个集合, 集合中的元素是污点标签, 污点标签表示为二元组{type, value}, 其中, type标识污点来源的类型, 一般可分为文件、网络、注册表或用户自定义4种; value表示具体的标签值, 用以区分不同的污点数据, 例如, 对于从文件中读取的污点数据, 则可以用value来标记污点数据在文件中的偏移.

本文定义了一组与污点相关的元操作, 可对变量进行相应的操作.

定义1(SetTaint(t, S)).对变量t设置污点属性.S为污点标签的集合, 其中, t表示内存中的某个地址或寄存器中的某个字节, 该过程执行完成后, t成为污点数据, 其污点属性为集合S.

定义2(AddTaint(t, l)).为变量t添加污点标签l.若t本来是污点数据, 则该操作向t的污点属性集中添加一个新标签元素l; 否则, 新建一个污点标签集合S={l}, 并将t的污点属性设置为S.

定义3(DelTaint(t, l)).为变量t删除污点标签l.若t的污点属性中含有l, 则将其删除; 否则, 不做任何操作.

定义4(DelTaint(t)).将变量t的污点属性全部删除, 则t将不再是污点数据.

定义5(GetTaint(t).获取变量t的污点属性, 返回t的污点标签的集合.

定义6(VerifyTaint(t)).判断变量t是否为污点数据, 返回值为布尔型.

本文还定义了一组与污点属性相关的元操作(如图 1所示).

Fig. 1 Operation of taint property 图 1 污点属性操作

●   Union(S1, S2):表示将两个污点标签集合做并集运算;

●   Copy(S1, S2):表示先将S1中的元素清空, 再将污点标签集合S2中的元素复制到S1中;

●   Del(S):清空污点标签集合S中的所有元素, S成为空集.

2 执行踪迹离线索引方法

本文基于执行踪迹的离线索引进行污点分析, 目的在于提高污点分析的效率.其主要思想是:首先, 使用动态插装工具来跟踪程序执行, 把执行的状态信息记入踪迹(trace)文件中; 然后, 离线地分析踪迹文件, 并建立索引文件.在污点传播过程中, 则只需关心与污点数据相关的操作, 与污点数据无关的指令可直接跳过, 从而节省大量的分析时间.

本文包含4类索引, 分别是函数调用索引(CALL)、返回地址索引(RET)、程序指令地址索引(EIP)及内存地址索引(MEMORY).其中,

●  函数调用索引、返回地址索引用于快速定位函数调用及函数的边界.对于有些函数(如CreateFile), 无需步入函数跟踪污点数据, 为此类函数建立一个白名单(white list), 当调用函数位于白名单中时, 可通过这两个索引直接跳过即可;

●  内存地址索引用于根据内存访问地址直接定位到访问该地址的指令.污点数据被引入后, 通常经过很长的指令周期后才可能被再次引用.通过内存地址索引, 可搜索到访问污点数据所在内存地址的指令, 从而跳过其他的无关指令;

●  指令地址索引根据指令地址快速定位该指令, 在某些支持JIT(just in time)编译执行的程序中, 污点数据可能直接被复制到指令的操作数中, 因此需要结合指令地址的索引来保证污点传播算法的准确性.

2.1 函数调用索引与返回地址索引

在解析Trace文件过程中, 如遇到函数调用(call)指令, 将其压入函数调用栈中, 并且将函数调用深度增1.对于每个线程, 都维护一个函数调用栈.接下来, 遇到每条指令都进行比较, 判断其是否是函数调用指令的下一条指令(即返回后的下一条指令):若是, 则认为它是该函数调用指令的返回地址, 并将函数调用深度进行调整.如果该返回地址与函数调用栈中的栈顶元素相匹配, 则函数调用深度减1;否则, 需减去它到栈顶的距离, 它到栈顶的元素全部出栈(如图 2所示).把函数调用指令及其返回指令在Trace文件的偏移、函数调用深度、线程号均记入函数调用索引文件中.

Fig. 2 Operation of call stack 图 2 调用栈操作

返回地址索引的主要作用是为了根据返回地址反向查找其函数调用指令的地址.当函数调用索引文件生成完成后, 通过读取函数调用索引文件, 将返回指令在踪迹文件中的偏移作为关键字进行排序, 然后写入返回地址索引中.

由于函数调用索引与返回地址索引中的记录都是有序的, 且每个索引记录的大小都是固定的, 因此可使用二分查找算法(binary search)来查询, 时间复杂度为log2(n), n为索引记录的个数.

结合函数调用索引和返回地址索引, 可快速地确定函数边界, 如果函数包含在用户定义的白名单中, 则不需要对其作污点分析, 可直接根据函数边界跳过该函数过程, 因而可极大地提高污点分析的效率.白名单是一个函数列表, 具有两种表示形式:一种是模块名和偏移:{Module:Offset}, 另一种是函数名称.这两种方式都可唯一标识函数, 函数名称便于用户设定, 但需要符号信息的支持.

算法1中确定函数边界的方法是:给定指令的偏移, 先判断其是否为函数调用指令:若是, 则直接读取函数调用索引得到其返回地址所在偏移; 否则, 先往下查找返回指令(ret或retn), 找到后在返回地址索引中查找对应的函数调用所在偏移.如果未找到, 则往上寻找函数调用指令, 直到找到函数调用指令为止.注意:在往上查找函数调用指令时, 如遇到返回指令, 则需查找到对应的函数调用指令, 并直接跳过该函数继续向上查找.

算法1.确定函数边界的算法.

输入:目标指令所在偏移;

输出:函数的边界(即调用地址和返回地址).

begin

1    re=DecodeInsn(addr)

2    if IsCallInsn(re) then

3      FindReturnByCallIndex(addr)

4    else

5      while (addr < MAX_ADDR) do

6        re=DecodeInsn(addr)

7        if IsReturnInsn(re) then

8          success=FindCallByRetIndex(addr)

9        endif

10      endwhile

11      if success!=TRUE then

12        while (addr > MIN_ADDR) do

13          re=DeocdeInsn(addr)

14          if IsCallInsn(re) then

15            FindReturnByCallIndex(addr)

16          endif

17        endwhile

18      endif

19 endif

end

2.2 内存索引与指令地址索引

内存索引可快速定位访问指定内存地址的指令记录, 内存索引的生成方法是:将内存地址空间分成页, 每页的大小为PAGE_SIZE(默认大小为32KB).页内的所有地址对应同一个队列, 队列中的每个元素为在踪迹文件中偏移的区间(interval), 表示该内存页中的某些地址落入这个范围中.当某条指令所在文件偏移与其所在队列的最大文件偏移相差超过阈值OFFFSET_THRESHOLD(默认为1024B)时, 此队列添加一个新的区间, 其上界与下界相等, 都为该指令在Trace文件中的偏移.若未超过此阈值, 则修改队列中最后一个区间的上界即可.

查询内存索引的过程:先对所需查找的内存地址计算页号, 使用页号查找内存索引, 查找到对应的分页后取出对应的地址区间队列, 遍历所有地址区间内的指令记录.如果指令访问内存的地址与要查找的内存具有交集, 则返回该指令的位置.

其中, PAGE_SIZEOFFSET_THRESHOLD的值是根据实际程序的测试得出的经验值, 以CVE-2011-0558漏洞的分析过程作为选择经验值的样本, 跟踪所得踪迹文件的大小是7.7GB.从表 1的数据可看出:若PAGE_SIZEOFFSET_THRESHOLD的值越小, 则生成的索引文件越大, 但分析所用的时间也越少; 反之, 生成的索引文件越小, 但分析所用时间越多.因此, 当PAGE_SIZE为32KB, OFFSET_THRESHOLD为1024B时, 污点分析的效率最高, 且生成索引的大小也在可接受范围.

Table 1 Experiment of choosing empirical value 表 1 经验值选取实验

表 1中, #PS表示PAGE_SIZE, #OT表示OFFSET_THREASHOLD, #R表示调用内存索引间隔的大小, #Size表示生成索引的大小, #Time表示污点传播所使用的时间.内存索引的查询算法见算法2.

算法2.内存索引查询算法.

输入:所需查找目标内存地址;

输出:访问目标内存地址的所有指令位置.

begin

1    IndexQuery=CaculateIndex(QueryMemoryAddr)

2    RangeQueue=GetRangeQueue(IndexQuery)

3    for range in RangeQueue do

4      (LowAddr, HighAddr)=range

5      for addr in [LowAddr, HighAddr] do

6      MemoryRange=ReadInsnRecord(addr)

7        if Intersection(Memoryrange, QueryMemoryAddr)!=nil then

8          AddList(addr)

9        endif

10      endfor

11 endfor

end

2.3 黑白名单机制

本文设计了较灵活的用户配置机制, 其中, 通过黑名单机制, 可动态地在某个程序点自定义地进行污点的引入或消除.通过白名单机制, 可跳过一些与污点无关的函数, 以提高污点分析的效率.对于当前有些程序, 污点引入与文件读取的关联性极其隐蔽.如LibTiff库, 其对图片文件的处理流程为:首先, 将图片全部载入其内存中; 然后, 使用自写的读取函数(如TIFFGetField)对内存中的图片数据进行解码.由于图片自身的数据大多经过压缩, 解码过程常将少于4字节的机器码解码为一个整数, 若按照以往的方法, 只对ReadFile函数下断, 则无法取得预期的效果.本文为解决该问题, 设计了一个方便的接口, 用户可根据该接口提供参数, 以供在污点分析过程中机动地引入或消除污点数据.用户提供的参数包括:需下断的函数名或函数地址、需变动污点的地址、需变动污点的大小、引入污点或消除污点.

具有上述机制后, 对LibTiff库的处理可直接对其自写的读取函数设置断点, 并将其返回值作为新的污点引入.黑名单的定义完全由用户提供, 需用户对分析的目标程序有初步的理解, 用户需通过逆向分析来确定需动态改动污点信息的位置, 自动化地确定该位置将作为下一步的研究工作.

对于有些函数(如CreateFile, GetProcessId等), 其执行过程并不会影响污点数据的变动, 因此无需步入函数跟踪污点数据, 为此类函数建立一个白名单(white list), 当调用函数位于白名单中时, 可通过这索引直接跳过即可.检测函数是否在白名单中的方法为:对于系统库函数, 可通过符号名直接对其进行匹配; 而对于无符号信息的用户自定义函数, 则可通过库名与偏移的形式进行比较.白名单可通过两种方法进行添加.

1)   通过库函数说明文档(MSDN)对函数的描述添加;

2)   在测试实际程序过程中, 根据测试中获得的经验添加.

白名单仅为提高污点分析的效率, 白名单中函数越多, 表明在污点分析过程中可跳过的函数也越多, 污点分析过程的效率也越高.

2.4 JIT翻译问题及解决方法

在某些支持JIT(just in time)编译执行的程序(如Flash)中, 污点数据可能直接被复制为指令的操作数, 成为指令的一部分.在该情况下, 代码与数据的概念冲突, 若按照传统的污点分析方法, 污点信息必然会发生丢失, 本文提出一种基于该问题导致污点信息丢失的解决方法.某些程序在执行过程中, 动态地生成代码并将这些代码复制到缓存区中, 然后跳转到缓存区中去执行, 这种执行方式称为JIT翻译执行.

JIT翻译执行可能会造成污点丢失的情况, 因为在生成代码时, 程序可能将污点数据直接以机器字节码的形式复制到缓存区中.如图 3所示, 污点数据被转化为该条指令中的立即数, 使用传统的污点分析算法无法感知这种转化, 因此必然会导致污点的丢失.

Fig. 3 Operation of JIT translation 图 3 JIT翻译操作

本文借助生成的指令地址索引来解决此问题, 当污点数据被转化为指令中的一部分时, 必然具备如下特征:

$ {{S}_{TAINT}}\cap {{S}_{EIP}}\ne \varnothing, $

其中, STAINT表示当前所有污点数据内存地址的集合, SEIP表示所有指令地址的集合.该语句是检查污点数据地址集与指令地址集是否发生重叠, 在污点传播过程中, 若检测到此类重叠, 则需继续将污点传播到正确的位置, 才能保证污点分析过程的顺利进行.

如果对每条指令作污点传播时都检测指令地址与当前污点地址是否发生重叠, 无疑会极大增加运行的时间.指令地址索引的引入, 则可有效提高污点分析算法的运行效率.

支持跳转的污点分析过程见算法3.

算法3.支持跳转的污点分析算法.

输入:当前指令位置;

输出:污点分析结果.

begin

1    while (CurrentLocation < MAX_LOC) do

2      if IsAllRegisterTaintEmpty() then

3        loc1=FindMemoryAccessByIndex(TaintSet)

4        loc2=FindEIPOverlapsByIndex(TaintSet)

5        loctojump=Min(loc1, loc2)

6        CurrentLocation=loctojump

7        continue

8      endif

9      TaintAnalysis(CurrentLocation)

10      CurrentLocation++

11 endwhile

end

综上所述, 提高污点传播的效率需结合内存索引与指令地址索引, 在污点传播过程中, 每执行一条指令时, 检测当前程序状态下是否所有寄存器的污点都为空:若是, 则根据内存索引可查询下一次访问污点内存的指令位置loc1.

如果需考虑JIT翻译执行的情况, 则需查询指令地址索引, 检测是否存在上述污点数据与指令地址重叠的情况, 并找到发生重叠的最近的指令位置loc2.此时, 可将当前污点传播位置跳到位置loc=Min(loc1, loc2).

3 系统实现

本文以上述基于执行踪迹离线索引的、支持污点标签、以字节为污点传播粒度的污点分析方法为理论依据, 使用2万余行C++代码实现了一个污点分析工具, 其中, 指令跟踪模块4千余行, 踪迹文件分析与索引生成模块1万余行, 污点分析模块6千余行.

图 4所示, 该系统包括4大模块.

Fig. 4 Structure of our system 图 4 系统结构图

1)   指令跟踪模块:监控程序执行, 并实时记录污点分析所需的上下文信息, 将其写入踪迹文件中;

2)   踪迹文件分析与索引生成模块:用来分析生成的踪迹文件, 并生成函数调用索引、返回地址索引、内存索引和指令地址索引;

3)   污点分析模块:在踪迹文件上进行离线的污点分析;

4)   漏洞检测模块:在污点分析完成后, 根据特定漏洞模式来检测漏洞, 并生成报告.

3.1 指令跟踪模块

该模块使用动态插装工具来对实际程序进行插装, 监控其执行过程.本文的实现是基于英特尔公司的二进制插装工具Pin[2-6], 根据其提供的用户接口, 为污点分析实现了一个相应的插装工具.指令跟踪模块包括3部分.

(1) 增量记录寄存器上下文

踪迹文件中, 指令记录占绝大多数, 其中以寄存器的值所占空间最大.为减少踪迹文件所占的磁盘空间, 本文使用增量式的记录方法, 对每条指令只记录当前指令引用或修改的寄存器的值.与记录所有寄存器的值的方法相比, 该方法所占存储空间约为前者的1/32.通过实现相应算法, 向前或向后遍历, 即可方便地推算出某个程序状态所有寄存器的值.

(2) 外部输入与内存映射

通常情况下, 将外部输入看做是污点来源, 例如文件中的某些字段、网络包中的某些字节.程序将外部输入读进内存, 并引入污点数据, 因此需映射外部输入到内存{IaM}, 以获得污点数据的内存地址.通过劫持诸如读取文件、接收网络数据包及读取注册表信息等系统函数, 并根据其返回参数, 可生成外部输入与内存地址之间的映射.表 2归纳了一些较常见的外部输入方式, 并说明了其参数与返回值.

Table 2 External input of several functions 表 2 外部输入函数

(3) 踪迹文件生成

踪迹文件中包括两类记录:① 模块记录, 记录模块加载时的信息; ② 指令记录, 记录当前指令的信息, 包括时间戳、线程号、指令码、内存访问地址及增量寄存器的上下文信息.为优化程序在动态插装下的执行效率, 应尽可能地提高I/O效率, 本文使用了延迟写的记录方式, 即:每次指令执行前先将其存入缓存(cache)中, 待缓存填满后再写入踪迹文件中.

3.2 踪迹文件分析与索引生成模块

踪迹文件生成后, 需对其进行离线分析, 根据记录的文件格式进行解析.在此过程中, 同时生成4种索引:函数调用索引、返回地址索引、内存索引和指令地址索引, 这4种索引的生成与查询方法已在上一节中描述.

踪迹文件分析完成后, 可提供如下功能:获取模块信息, 取得所有模块的模块名、加载地址; 获取线程信息, 取得所有线程的线程号、线程起始地址, 根据在踪迹文件中的所在偏移取得指令记录; 支持符号信息, 可根据微软提供的符号信息, 将对应的地址转化为符号名.

3.3 污点分析模块

指定外部输入中的某些字节, 通过外部输入与内存的映射, 可得到其在内存中的位置与大小, 由此通过SetTaint原语引入污点源, 由引入污点的位置开始进行污点传播过程.

污点元可以是寄存器或内存, 为支持多线程的程序, 寄存器必须是线程相关的.为统一管理污点标签, 我们实现了统一的污点标签管理方法, 把所有污点元的污点标签统一进行管理, 内存使用内存地址作为标识, 寄存器的标识使用高于2G空间的内存地址来表示.将寄存器ID与相应线程的ID经哈希运算得到的值, 作为寄存器的标识来操作对应的污点标签.

●  对于内存:MemTaint;

●  对于寄存器: $\boldsymbol{\mathcal{H}}$ (RegID, Tid)↦Taint.

污点传播过程直接在汇编指令上进行, 需考虑指令的语义和副作用.汇编指令大致可归纳为3种类型的操作:1) 数据传输指令, 如MOV, PUSH, XCHG操作; 2) 运算指令, 如ADD, SHL, OR操作; 3) 跳转指令, 如Jmp, Call操作.对于污点传播主要考虑前两种类型的指令.

定义通用的污点传播语义如下.

●  数据传输指令: $\frac{mov\text{ }dst, \text{ }src}{{{T}_{dst}}\leftarrow {{T}_{src}}};$

●  一元运算指令: $\frac{Uniop\text{ }src}{{{T}_{src}}\leftarrow {{T}_{src}}};$

●  二元运算指令: $\frac{Binop\text{ }dst, \text{ }src}{{{T}_{dst}}\leftarrow UNION({{T}_{dst}}, {{T}_{src}})}.$

对于大部分指令, 都可使用通用的污点传播方式, 有些指令则需作特殊处理, 如移位操作SHL, SHR, SAR和浮点栈操作.

●  移位操作.由于本文所实现的污点分析方法是基于字节粒度的, 对于移位操作, 如果移动的位数大于8位, 则进行污点传播.例如, 一个4字节的整数向左移8位, 将低3个字节的污点标签复制到高3个字节, 并且将最低字节的污点属性消除;

●   FPU浮点寄存器栈.对于浮点寄存器栈也需要作特殊处理, 如FPU寄存器的栈顶始终为ST(0), 对于出栈操作FSTP, 除了将栈顶ST(0) 的污点属性传输到目的操作数外, 还需将所有栈中元素向上移一个位置.入栈操作FLD则相反, 需要先将所有栈中元素向下移一个位置;

●  扩展操作.对于类似MOVZX, MOVSX的扩展操作, 除了将源操作数扩展成4个字节的整数外, 还需要将相应高字节部分的污点属性都消除;

●  指令的副作用.有些指令具有副作用, 如REP操作影响寄存器ECX的值, 大部分运算操作影响标志寄存器EFLAGS的值, 在污点传播时必须加以仔细考量.

在污点传播过程中, 需要进行污点消除以避免污点的非法扩散, 这涉及以下几种情况:① 指令清空污点元, 如XOR x, x类型的指令; ② 污点元被覆盖, 如使用数据传输指令, 将常数赋值给污点元, 或将一块不具有污点属性的内存传递给污点元; ③ 指令的副作用, 如CDQ指令会默认把寄存器EDX清空.

表 3中列出一些污点消除的情况.

Table 3 Several examples of taint elimination 表 3 一些污点消除示例

为达到分析精度和分析效率的折衷, 本系统支持用户自定义配置污点传播的规则, 可供用户根据自己的需要来灵活配置的选项有:① 如果内存地址为污点, 其存储的值是否也认为是污点数据; ② 是否将循环操作的计数作为污点数据; ③ 是否考虑标志寄存器的污点属性; ④ 当移位操作的移位个数是污点时, 结果是否也认为是污点.

本系统支持用户自定义的白名单(white list)与黑名单(black list):可通过白名单的方式, 将不需要进行污点传播的函数列出, 遇到此类函数时即可直接跳过, 以提高污点分析的效率; 还可提供一个黑名单, 用户可自定义这些函数的污点传播规则, 如strlen函数, 如果其参数为污点数据时, 可将函数的返回值也置为污点数据.

3.4 漏洞检测模块

污点分析过程完成后, 可以确定污点数据从污点源传播到了哪些目标位置.一般来说, 污点数据是可控的, 因此, 当污点数据以参数形式传入某些函数时, 则其可能导致漏洞的出现.

本文主要考虑3种漏洞模式, 分别是内存任意读写、内存分配不当导致的溢出问题以及调用危险函数, 这3种漏洞模式适用于污点分析方法.对于内存任意读写, 只需检测是否将污点数据写入由污点数据表示的内存地址中.这一模式可描述为[Taint]←Taint.

对于内存分配不当, 只需检测分配内存的函数, 如alloc, malloc, operator new, VirtualAlloc等, 其参数是否为污点数据.

有些危险函数如memcpy, strcpy, memmove等函数也容易导致溢出漏洞的出现, 因此也需检查其参数是否为污点数据.此外, 还可由用户自定义危险函数, 若其参数为污点数据时, 则进行检测.

4 实验结果

为证明本文提出的污点分析方法行之有效, 本文选取了近年来若干较典型的漏洞作为测试样本集进行测试.选取样本漏洞的依据为:此类样本的漏洞类型多为整数溢出漏洞, 且漏洞成因与文件输入直接相关, 从理论上可使用污点分析方法进行检测.

在测试前, 需对这些漏洞进行分析, 使用相应的样本文件作为输入, 检测其是否能将污点数据传播到对应的漏洞触发位置, 进而由本文所提出的方法进行检测.

为与传统的漏洞检测方法进行比较, 采用伯克利大学研发的原型系统BitBlaze[7-10]中的TEMU[10-12]作为比较对象, TEMU中所使用的污点分析方法具有一定代表性, 并且开放源代码, 但其自身运行于Linux操作系统平台, 并且与虚拟机QEMU结合, 为与本文中的方法进行比较, 需对其进行如下改动:(1) 使其可兼容于Windows系统平台; (2) 将在线的污点分析过程改为离线.由于未对TEMU的污点分析的核心代码改动, 因此, 修改后的系统可如实地反映TEMU的分析效率.

实验环境为CPU:Intel Core i5-3337U 1.8GHz; 内存:4GB; 操作系统:Windows 7 SP1(64位).

通过表 4中的实验数据可知:相比传统的污点分析工具来看, 在验证漏洞方面, 本文提出的污点分析方法具备较强的漏洞检测能力, 这是由于:

Table 4 Experiment of vulnerabilities detecting 表 4 漏洞检测实验

1)  本文提出的方法加入的黑名单机制使其在检测漏洞方面更加具有灵活性, 使其可检测的漏洞模式包括内存任意读写、内存分配不当、调用危险函数, 较TEMU更多; 例如对CVE-2010-0304漏洞, 需检测的危险函数为tvb_get_nstringz, 该函数第3个参数为读取的长度, 由网络数据包中指定, 为污点数据; 第4个参数为栈变量.当第3个参数大于第4个参数时, 造成栈溢出;

2)  本文提出的方法解决了JIT(just in time)翻译执行导致的污点丢失问题, 因此可处理使用了JIT机制的程序.例如CVE-2012-0774漏洞, 若不解决JIT翻译问题, 则会导致污点信息在传播过程中丢失, 进而无法检测该类漏洞.

在执行效率方面, 本文提出的基于执行踪迹离线索引的污点分析方法更具有明显的优势, 平均比传统的污点分析方法快5倍以上.

我们将本文所提的方法部署在漏洞挖掘系统平台中, 已发现大量软件漏洞, 其中发现了金山WPS、Xnview等软件中10个0day漏洞, 已提交给国家信息安全漏洞库.出于安全性与厂家协作等考虑, 故不在此批露这些漏洞的细节.

4.1 讨论

二进制代码的污点分析方法是一种近似准确的数据流分析方法, 可通过污点分析方法观察到敏感数据流向何处, 如果其传入敏感位置时, 则可能导致漏洞.然而, 由于污点分析方法只关注数据流向而不关心数据的值, 导致在有些情形下可能产生污点分析的不确定性, 即污点分析方法的盲区.在实际测试中, 发现污点分析算法中, 盲区主要包含以下3种情况.

① 污点数据扩散

考虑以下这种情况:

$ \left\{ \begin{array}{*{35}{l}} x=y+z \\ z=x-y \\ \end{array} \right.. $

假设y为污点数据, 那经过第1条语句执行后, 根据污点传播算法, x也成为污点数据.同理, 当执行完第2条语句后, z也成为污点数据.然而从语义上看, z的值并未发生变化, 永远保持其原有的值, 因此, 将其认为是污点数据是错误的.类似这种情况, 将会引发污点数据的扩散.

② 污点数据丢失

污点信息同样可能会由于语句中的副作用发生丢失, 如strlen函数, 当该函数的参数为污点数据时, 理论上该函数的返回值的大小也应被认为是污点数据.但是按照传统的污点传播算法, 这类污点信息必然会丢失.本文提出函数黑名单的目的就是想解决这类型的问题, 但如果用户内联实现strlen函数, 则无法通过此方法解决.类似地, 循环结构中, 循环上界与循环次数之间也可被认为是相关的, 尽管不少研究者[13, 14]提出了对循环结构的识别, 尽可能地弥补由循环引起的污点信息丢失, 但仍无法适用于全部情况.

③ 污点传播不当

污点传播不当, 同样是由于污点分析方法只关注数据流而不关心其值所引起的问题, 考虑如下的情况:

$ \left\{ \begin{array}{*{35}{l}} x=y\times z \\ y=x \\ \end{array} \right.. $

假设y为4字节整数, 其低两个字节为污点数据, 当这两条语句执行完成后, 很难确定y到底含有几个字节的污点数据, 因为其结果与z的值相关.如果z的值为1, 则y的污点信息未发生变化; 而如果z为0, 则y应该不再具有污点属性.fscanf函数中也存在这样的问题, 以下是其内部的几行代码:

$ \left\{ \begin{array}{*{35}{l}} x=SHL(x, 4) \\ ... \\ x=SHL(x, 4) \\ \end{array} \right.. $

SHL为左移指令, 表示连续两次将x左移4位, 两次左移达到8位, 将发生对字节的污点传播.然而本文中实现的方法是以字节为粒度, 只对左移8位以上才对污点数据进行移位.对这种情况无法感知, 因此会发生污点信息传播不当的问题.

5 相关工作

近年来, 国内外很多学者都围绕污点分析方法进行了较深入的研究[12-22].Yin等人[13]提出了基于QEMU虚拟机的扩展平台TEMU, 可解决动态分析的困难, 便于在其上进行程序分析.TEMU使用全系统的视角, 可分析内核中的活动与多进程间的交互; 提供了很好的隔离性与透明性, 使恶意程序难以检测到分析环境并影响分析结果, 以细粒度的方式进行深度分析.

Schwartz等人[15]描述了一种基于中间语言上的污点传播策略.

1)  污点引入:实现了一个简单的用户输入源——get_input调用, 表示从系统调用、库调用返回的结果, 不同的输入源的污点引入规则也不同;

2)  污点检查:污点的状态值用以确定程序的异常行为, 通过添加此类规则到操作语义的前提条件中进行检查;

3)  污点传播策略:内存操作包括内存的地址和内存单元两类值, 污点传播策略分别追踪内存地址和内存单元的值;

4)  污点消除.如程序函数计算的结果恒为常量时, 则需要消除污点.

Enck等人[16]描述了TaintDroid, 一个基于动态污点传播方法的移动手机的扩展平台, 可追踪私密的敏感信息流.其特性包括:(1) 借助虚拟机的解释器提供变量级的追踪, 使用解释器提供的变量语义来避免Intel x86指令的污点信息扩散.对变量进行修改, 并维护其污点标记; (2) 实现应用程序间的消息追踪, 可减小进程间通信的成本; (3) 对于系统提供的库, 使用函数级的追踪.直接运行库中的代码, 并在其返回时修改污点传播策略, 需事先可知函数的语义信息; (4) 使用文件级的追踪方法, 确保持久信息保持其正确的污点标记.

Kang等人[17]提出一种动态的污点传播方案DTA++, 包括两个阶段:首先通过诊断, 产生不完全污点的分支生成规则, 并确定离线分析所需额外的传播; 其次, 在以后动态污点分析中应用那些规则.其基本原理是:查找不完全污点的控制流的路径, 由于确定输入需更多细粒度的信息, 使用符号执行和基于路径谓词的方法.在符号执行中, 指令执行的踪迹对应包括一系列分支判定的程序路径约束.查找分为两部分:检测谓词Φ确定一个路径子串中是否含有引发错误的隐式流; 然后查找Φ中第1个路径前缀.

北京大学的王铁磊等人提出了TaintScope[18]和IntScope, 其中, TaintScope[19]用于定位程序中的校验和, 而IntScope的主要贡献是利用污点分析方法来检测整数溢出漏洞.其实现方法是:通过反编译方法, 将二进制代码翻译成为静态单赋值形式的中间表示, 建立控制流图和调用图, 使用深度优先遍历控制流图.对于分支, 则使用求解器计算当前路径约束是否满足该分支的条件.

北京航空航天大学的忽朝俭等人[20]提出并深入分析了驱动程序中频繁出现的写污点值到污点地址漏洞模式, 提出了一种针对该种漏洞模式的基于反编译、数据流分析和污点分析的检测方案, 并实现一款既可分析本地二进制代码, 也可分析C源代码的原型工具.

上述传统的污点分析方法为本文的研究工作提供了坚实的理论基础和实现细节, 但其中大多数污点分析方法不支持浮点指令, 执行效率较低, 且传播的精度也不够高.本文为解决这些问题, 在前人的工作基础上进行更进一步的探索与研究.

6 结束语

本文实现了一种基于执行踪迹离线索引的污点分析方法, 支持污点标签, 并以字节为粒度进行污点传播.离线索引可跳过与污点数据无关的指令, 极大地提高了污点分析的效率.本文首次描述并解决了由JIT翻译执行导致的污点丢失问题.利用污点标签, 可标识污点来源于何种外部输入及其对应外部输入的哪些字节.以字节为粒度增加了污点传播的精度, 保证污点信息以较合理、准确的方式从源操作数传递到目的操作数.

利用本文工具与TEMU在12个真实软件漏洞的对比检测结果表明:本文提出的污点分析方法更为完善, 具备更强的漏洞检测能力和更高的分析效率, 可检测和验证大量的已知漏洞.目前, 本文工具已部署到检测0day漏洞的系统中.本文最后讨论了在实验过程中遇到的一些棘手的问题, 这些问题可能导致污点信息的传播发生偏差, 期望在以后的研究过程中逐步解决这些问题.

参考文献
[1]
Mei H, Wang QX, Zhang L, Wang J. Software analysis:A road map. Chinese Journal of Computers, 2009, 32(9): 1697–1710(in Chinese with English abstract). [doi:10.3724/SP.J.1016.2009.01697]
[2]
Luk C, Cohn R, Muth R, Harish P, Klauser A, Lowney G, Wallace S, Reddi VJ, Hazelwood K. Pin:Building customized program analysis tools with dynamic instrumentation. In:Proc. of the ACM Conf. on Programming Language Design and Implementation. New York:ACM Press, 2005. 190-200.[doi:10.1145/1065010.1065034]http://portal.acm.org/citation.cfm?id=1065010.1065034
[3]
Lueck G, Patil H, Pereira C. PinADX:An interface for customizable debugging with dynamic instrumentation. In:Proc. of the IEEE/ACM Int'l Symp. on Code Generation and Optimization. New York:ACM Press, 2012. 114-123.[doi:10.1145/2259016.2259032]http://dl.acm.org/citation.cfm?doid=2259016.2259032
[4]
Roy A, Hand S, Harris T. Hybrid binary rewriting for memory access instrumentation. In:Proc. of the 7th ACM SIGPLAN/SIGOPS Int'l Conf. on Virtual Execution Environments. New York:ACM Press, 2011. 227-238.[doi:10.1145/1952682.1952711]
[5]
Skaletsky A, Devor T, Chachmon N, Cohn R, Hazelwood K, Vladimirov V, Bach M. Dynamic program analysis of microsoft windows applications. In:Proc. of the Int'l Symp. on Performance Analysis of Software and Systems. Timisoara:IEEE, 2010. 389-400.[doi:10.1109/ISPASS.2010.5452079]http://dblp.uni-trier.de/db/conf/ispass/ispass2010.html
[6]
Patil H, Pereira C, Stallcup M, Lueck G, Cownie J. PinPlay:A framework for deterministic replay and reproducible analysis of parallel programs. In:Proc. of the 8th Annual IEEE/ACM Int'l Symp. on Code Generation and Optimization. New York:ACM Press, 2010. 1020-1034.[doi:10.1145/1772954.1772958]
[7]
Song D, Brumley D, Yin H, Caballero J, Jager I, Kang MG, Liang ZK, Newsome J, Poosankam P, Saxena P. BitBlaze:A new approach to computer security via binary analysis. In:Proc. of Int'l Conf. on Information Systems Security. Hyderabad:Springer-Verlag, 2008. 1-25.[doi:10.1007/978-3-540-89862-7_1]https://link.springer.com/chapter/10.1007/978-3-540-89862-7_1?no-access=true
[8]
Brumley D, Poosankam P, Song D, Zheng J. Automatic patch-based exploit generation is possible:Techniques and implications. In:Proc. of the IEEE Symp. on Security and Privacy. California:IEEE, 2008. 78-102.[doi:10.1109/SP.2008.17]
[9]
Yin H, Liang Z, Song D. HookFinder:Identifying and understanding malware hooking behaviors. In:Proc. of the 15th Annual Network and Distributed System Security Symp. San Diego:Internet Society, 2008. 103-119.
[10]
Caballero J, Yin H, Liang Z, Song D. Polyglot:Automatic extraction of protocol message format using dynamic binary analysis. In:Proc. of the 14th ACM Conf. on Computer and Communications Security. New York:ACM Press, 2007. 567-581.[doi:10.1145/1315245.1315286]
[11]
Yin H, Song D, Egele M, Kruegel C, Kirda E. Panorama:Capturing system-wide information flow for malware detection and analysis. In:Proc. of the ACM Conf. on Computer and Communication Security. New York:ACM Press, 2007. 103-119.[doi:10.1145/1315245.1315261]
[12]
Kang M, Poosankam P, Yin H. Renovo:A hidden code extractor for packed executables. In:Proc. of the 5th ACM Workshop on Recurring Malcode. New York:ACM Press, 2007. 327-341.[doi:10.1145/1314389.1314399]
[13]
Ma JX, Li ZJ, Hu CJ, Zhang JX, Guo T. Research of array type abstraction reconstruction in binary code. Journal of Tsinghua University:Science and Technology, 2012, 10(1): 1329–1334(in Chinese with English abstract). [doi:10.16511/j.cnki.qhdxxb.2012.10.003]
[14]
Ma JX, Li ZJ, Hu CJ, Zhang JX, Guo T. A reconstruction method of type abstraction in binary code. Journal of Computer Research and Development, 2013, 50(11): 2418–2428(in Chinese with English abstract). [doi:10.7544/issn1000-1239.2013.20111676]
[15]
Schwartz J, Avgerinos T, Brumley D. All you ever wanted to know about dynamic taint analysis and forward symbolic execution. In:Proc. of the IEEE Security and Privacy Symp. 2010. 723-734.[doi:10.1109/SP.2010.26]
[16]
Enck W, Gilbert P, Chun BG, Cox LP, Jung J, McDaniel P, Sheth AN. TaintDroid:An information-flow tracking system for realtime privacy monitoring on smartphones. In:Proc. of the USENIX Symp. on Operating Systems Design and Implementation. Vancouver:USENIX, 2010. 817-822.[doi:10.1145/2619091]
[17]
Kang M, McCamant S, Poosankam P, Song D. DTA++:Dynamic taint analysis with targeted control-flow propagation. In:Proc. of the 18th Annual Network and Distributed System Security Symp. San Diego:Internet Society, 2011. 913-926.http://dblp.uni-trier.de/db/conf/ndss/ndss2011.html
[18]
Wang TL, Wei T, Gu GF, Zou W. TaintScope:A checksum-aware directed fuzzing tool for automatic software vulnerability. In:Proc. of the 2010 IEEE Symp. on Security and Privacy. California:IEEE, 2010. 497-512.[doi:10.1109/SP.2010.37]http://ieeexplore.ieee.org/xpl/abstractKeywords.jsp?reload=true&arnumber=5504701&contentType=Conference+Publications
[19]
Wang TL, Wei T, Lin ZQ, Zou W. IntScope:Automatically detecting integer overflow vulnerability in x86 binary using symbolic execution. In:Proc. of the 16th Network and Distributed System Security Symp. San Diego:Internet Society, 2010. 333-347.
[20]
Hu CJ, Li ZJ, Guo T, Shi ZW. Detecting the vulnerability pattern of writing tainted value to tainted address. Journal of Computer Research and Development, 2011, 48(8): 1455–1463(in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201108019.htm
[21]
Babak Y, Saumya D. Symbolic execution of obfuscated code. In:Proc. of the 22nd ACM SIGSAC Conf. on Computer and Communications Security. New York:ACM Press, 2015. 732-744.[doi:10.1145/2810103.2813663]
[22]
Michelle W, David L. IntelliDroid:A targeted input generator for the dynamic analysis of android malware. In:Proc. of the 22nd Network and Distributed System Security Symp. San Diego:Internet Society, 2016. 481-496.
[1]
梅宏, 王千祥, 张路, 王戟. 软件分析技术进展. 计算机学报, 2009, 32(9): 1697–1710. [doi:10.3724/SP.J.1016.2009.01697]
[13]
马金鑫, 忽朝俭, 李舟军, 张俊贤, 郭涛. 二进制代码中数组类型抽象的重构方法. 清华大学学报:自然科学版, 2012, 10(1): 1329–1334. [doi:10.16511/j.cnki.qhdxxb.2012.10.003]
[14]
马金鑫, 李舟军, 忽朝俭, 张俊贤, 郭涛. 一种重构二进制代码中类型抽象的方法. 计算机研究与发展, 2013, 50(11): 2418–2428. [doi:10.7544/issn1000-1239.2013.20111676]
[20]
忽朝俭, 李舟军, 郭涛, 时志伟. 写污点值到污点地址漏洞模式检测. 计算机研究与发展, 2011, 48(8): 1455–1463. http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201108019.htm