一种粗细粒度结合的动态污点分析方法
2014-06-02史大伟袁天伟
史大伟，袁天伟
一种粗细粒度结合的动态污点分析方法
史大伟，袁天伟
(江南计算技术研究所，江苏 无锡 214083)
针对当前污点分析工具不能兼顾速度和精确度的缺陷，研究并实现一种粗细粒度结合的二进制代码动态污点分析方法。对比粗粒度污点分析和细粒度污点分析的实现过程，提出两者结合的新型分析框架。预先在线执行粗粒度污点分析以筛选有效指令，之后离线执行细粒度污点分析以计算污点信息。根据粒度的差异分别建立粗细粒度污点数据的引入标记方法，制定粗细粒度条件下的数据流和控制流传播策略，设计离线轨迹记录结构作为粗细粒度污点分析的传递文件。在原型系统上的测试结果表明，该方法通过在线粗粒度模式保证了污点分析信息采集的快速性，同时采用离线细粒度模式以合理的时间消耗提升了污点分析的精确度。
粗粒度；细粒度；动态污点分析；离线轨迹；污点传播；二进制
1 概述
污点分析(taint analysis)是指对非信任来源的数据进行标记，并追踪其在程序执行中的传播过程，以达到获取关键位置与输入数据关联信息的分析方法[1]。随着网络化、信息化的不断推进，来自于网络的威胁越来越大，并逐渐呈现以下特征：恶意攻击代码变种越来越多，攻击方式隐蔽性越来越高明，攻击行为组织性专业性越来越强。网络安全遭受的威胁日益加剧，防范难度日愈严峻。污点分析从网络恶意攻击的本质入手，以一种溯源式的方式判断外部传递数据对跳转地址、返回地址、函数指针的影响，直接检测网络恶意攻击的进行。
动态污点分析(Dynamic Taint Analysis, DTA)[2]能够在程序运行过程中，以运行时机器指令流为依据，对目标软件的非信任数据进行信息流跟踪，监控软件系统安全状态。动态污点分析是污点分析的主要模式，被广泛运用于信息安全验证、恶意代码分析[3]、隐私泄露分析、协议格式逆向分析[4]等领域。分析时，首先将未获取安全认证的输入数据标记为污染源，然后根据程序实时指令和运行时状态信息，依据制定的污点流传播规则，分析污染源数据在寄存器和内存中的传播过程，同时在程序敏感字段设置检测点，当检测到有污染源数据导入时采取相应的安全决策措施。
当前动态污点分析技术按分析粒度可以划分为细粒度(fine-grained)[5]动态污点分析技术和粗粒度(coarse-grained)[6]动态污点分析技术。粗粒度污点分析一般用于异常行为检测，例如对于某一端口的恶意扫描或其他不正常行为；细粒度污点分析则主要用于检测程序的脆弱性攻击点。粗粒度污点分析具有分析速度快、占用存储空间小的优点，可用于检测污点数据有无问题；细粒度污点分析精度高，可解决数据流的回溯问题。现阶段动态污点分析均采用单一解析模式，都会碰到污点分析不精确、验证测试代价大或代码解析效率低、空间需求过大的难题。
针对现有污点分析方法的不足，本文提出一种面向二进制代码的粗细粒度结合的动态污点分析方法，利用粗粒度污点分析技术对目标程序进行实时监控和预分析，实时记录其执行指令流及相关寄存器和内存信息，同时依据策略分析污点传播状态。当满足中断策略时，输出现有指令流记录信息至离线细粒度污点分析系统，快速高效地分析字节粒度的污点源关联性，并执行测试验证或安全修复。
2 粗细粒度结合的动态污点分析
2.1 动态污点分析原理
动态污点分析的主要目的是解决软件安全问题，而导致软件安全性问题的主要原因是软件自身在设计、实现和配置时引入的各种安全漏洞(也称脆弱性)。安全漏洞是指软件中违背安全策略并导致安全危害的不足或缺陷，在一般条件下，可信程序在无外界干预的条件下，其运行可认为是可控的。软件安全漏洞的出现在于程序自身，而其利用则以外部数据为诱因。
动态污点分析以信息流传播为主要分析对象，着重跟踪外部引入数据在运行中的传播活动，其主要的分析过程包括污点标记、污点传播、污点检测。运行时污点状态信息是动态污点分析的基础和对象，与污点分析的三大模块密切相关。
定义1运行时污点状态(taint status)。在污点标记和污点传播中，对每个内存(MEM)、寄存器(REG)和标志位(eflags)获取污点信息，该污点信息的集合统称为运行时污点状态。指令的运行会触发的改变，在程序的运行过程中，随着污点信息的不断引入和传播，最终形成状态转换序列：=01…。
动态污点分析的框架结构如图1所示。
图1 动态污点分析框架结构
污点数据标记、污点数据传播和敏感点污点检测为3个平行的污点操作活动。运用HOOK机制获取指令流信息后，需结合当前运行时污点状态和指令信息判断：
(1)若该位置为敏感位置则进行污点检测，如果存在污点信息的不当使用则输出该信息。
(2)若为污点引入则采用污点标记策略，标记外部引入数据，同时更新。
(3)若为污点传播则依据指令内含的信息流传播策略指导执行并更新。
2.2 粗细粒度结合的污点分析框架
运行时污点状态提供了系统中的污点信息，依据记录信息的精细划分，将其区分为2种不同的粒度：粗粒度污点状态和细粒度污点状态，其蕴含的信息量不同，对应的污点分析目的也有所区别。对两者进行比较，结果如表1所示。
表1 粗细粒度污点分析对比
粗粒度污点分析是将所有外部输入的不可信数据源均标记为污点源，该污点源的标记是采用一种粗放式的标识方法，所有污点源为不区分的单一模式。而对于每个寄存器、内存地址和标志位，均只有2种状态：untainted和tainted。
细粒度污点分析需要标定和追踪每个污点数据单元。由于一个内存单元可能依赖于多个污点数据，因此需要用集合结构描述一个内存单元的污点属性。由污点属性可以回溯污点传播源头，在分析过程中，一般采用整型变量表示污点标签，并建立变量索引表。本文采用的细粒度污点分析的污点数据标记和污点个体描述均是以字节为单位。
粗粒度污点分析污点标记简单，污点信息存储空间小，分析速率快，而细粒度污点分析精度高，针对性强。本文结合粗粒度污点分析的高效性与细粒度污点分析的精确性，提出粗细粒度结合污点分析框架，具体设计如图2所示。
图2 粗细粒度结合的动态污点分析框架
污点分析的主要分析模式遵循图1的框架设计，本文按粗细粒度区分实现了2种污点分析方式，并以中断策略作为时空间隔标准，先粗后细、先有无后精准地实现快速高效的污点分析过程。中断策略可设置为程序运行结束或污点数据误用敏感点。
在本文构建的粗细粒度污点分析框架中，目标程序运行于客户操作系统中，以运行时的底层二进制执行指令作为分析对象，具有较强的系统无关性，适用于Windows、Linux、Mac OS等多种操作系统。同时虚拟的隔离环境提供良好的透明性，能分析各种类型的应用程序软件。该框架能较全面地应用于各类系统与软件的安全性分析，具有较好的普适性与可扩展性。
程序监控的指令流及运行时信息驳杂且繁多，其中包含众多图形界面接口调用、系统参数读取等非污点传播事务轨迹信息，真正有效的污点传播指令流较少。本文将繁杂的初运行时信息和指令流用于简单的粗粒度污点分析，以在线分析形式快速获取指令污点传播信息，同时记录污点传播的指令流及对应运行时信息，依据中断策略导出，之后转入离线状态的细粒度污点分析模块，利用高性能处理机进行分析。
2.3 污点标记策略
污点标记是污点传播的首要步骤，其标记方式极大地影响着污点传播处理与污点信息存储的效率。污点标记是将外部引入的数据标记为污点数据。本文采取粗细粒度区分的方式，制定2种污点标记策略：
(1)对于粗粒度污点分析，污点信息的标记值设定为tainted和untainted。污点源头标记的依据源于对程序运行时系统调用函数的监控，主要的监控函数包括文件输入open、read函数(Linux)、文件输入OpenFile、ReadFile函数(Windows)、网络输入send、recv、sendto、recvfrom函数等。利用HOOK技术监视系统调用，劫持目标系统函数调用信息，获取函数参数，解析参数含义，转向自定义函数调用处理，以获取污点源头输入。
(2)对于粗粒度污点分析，内存标记的状态空间仅为{tainted, untainted}，同时污点数据的引入和传播具有局部性的特征：污点数据通常分散存在于内存的某重点区域；污点数据的引入一般会集中在某块区域。故相应的粗粒度污点分析内存标记模型采用精简式集中管理，将所有涉污数据地址统一存储，运用段式污点标记方法，标识污点信息流的作用空间，可一定程度上降低内存消耗。
在本文中，内存中涉污数据段采用数据结构
表2 粗粒度污点分析存储模式
在细粒度污点分析中，以粗粒度分析后的涉污轨迹信息文件为对象，其污点的内存标记以字节为单位，并维护一个相对应的影子内存(shadow memory)[7]记录内存地址和污点属性的映射关系。影子内存为到的映射，记为{}，其中，为单点链式传播串中的状态快照，包含源污点数据标识表和依赖污点源数据结构体。
本文采用字节粒度的污点数据标识，标识号应用顺序整型的数字标号，标识号的集合构成源污点数据标识表，依赖污点源数据结构体采用有序二元决策图(reduced ordered Binary Decision Diagram, roBDD)[8]。
2.4 污点传播策略
动态污点分析的灵魂是污点信息流[9]的传播，信息流的传播是污染源在程序运行中扩散和蔓延的关键，污染源数据以信息流为载体，沿着信息流传播方向传递。伴随着信息流的不断传播，污点信息不断产生、传递和使用，可以说，信息流是污点数据传播的宿主，它是传播的支配者，要分析污染源的传播状态，需从宿主着手，分析信息流传播的方向性、范围度、时效性，进而重点跟踪污染数据的路径轨迹。本文动态污点分析的过程即从信息流传播入手，以执行时二进制汇编代码为分析对象，研究信息流传递的时空特性，获取状态信息和传播过程。
定义2污点信息流传播(Taint-flow Propagation, TFP)是程序运行时污点状态的变化过程，为运行时污点状态序列=01…中相邻链节点ts→ts+1的转移过程，其前趋状态ts为源状态，后趋状态ts+1为目的状态。
定义3污点传播策略(Taint Propagation Strategy, TPS)是一种预设定的规则，为执行指令操作到污点信息传播形式的映射集合。TPS={data-flow strategy, control-flow strategy}包含数据流[10]分析策略和控制流[11]分析策略。污点传播策略的完备性和正确性极大程度上决定了污点分析过程的精准度。
数据流分析主要分析由数据移动指令、算术逻辑运算指令引发的值转移过程，控制流分析主要分析由指令跳转引发的控制转移过程。数据流分析的主要对象为显式操作数(标准指令格式中的操作数)及隐式操作数(存在数据流转移但未在指令中标示的操作数，以标志位为代表)，其侧重点是通过解析指令，依据污点传播策略指导污染数据的传播。控制流分析大多针对跳转类指令，以分支路径跳转为研究内容，由于汇编指令中，条件跳转多数以标志位为判断，因此本文控制流分析的主要对象为跳转指令中的标志位污点信息。
本文将策略定义为模式和行为实体的集合strategy=
表3 动态污点分析策略
控制流传播分析旨在获取当前执行路径的污点约束，粗粒度污点标记信息极简单，其控制流污点信息只表明污点控制的有无性，分析意义并不明显，因此，本文重点设计了CTDPS、FTDPS和FTCPS。
本文依据汇编指令执行规则，将粗粒度分析条件下信息流传播模式(CTDPM)区分为以下5种：data in, data clear, eflags in, eflags set, NULL。过程分析中的污点传播模式均属于该类间集合。data in为存储单元数据流引入；data clear为存储单元数据流清除；eflags in为标志位数据流引入；eflags clear为标志位清除；NULL是空模式，为无污点流传递。图3展示了粗粒度信息流传播模式及具体示例。
图3 粗粒度数据流传播模式
粗粒度污点分析下信息流传播策略的行为实体极为简略，其实体集合仅含{settainted, setuntainted, NULL}3类操作，分别表示污点属性设定、污点属性消除和空操作。粗粒度条件下，污点属性信息为统一存储维护的，所以，将依据污点属性的更新，实时管理内存污点属性标识链表、寄存器污点属性标识顺序表和标志位污点属性字节。
细粒度分析条件下数据流传播模式(FTDPM)区分为以下6种：data in, data add, data clear, eflags in, eflagsclear, NULL。data in为存储单元数据流模式；data add为存储单元数据流添加；data clear为存储单元数据流清除；eflags in为标志位数据流引入；eflags clear为标志位清除；NULL为空模式。图4展示了细粒度信息流传播模式及具体示例。
图4 细粒度信息流传播模式
行为实体是针对污点属性的具体操作，本文在细粒度分析条件下，共定义了7种行为实体。该行为实体适用于数据流分析策略和控制流分析策略。其中，()为当前指令执行中引入的源污点数据条目；()为当前污染源集合，公式中行为实体5和行为实体6的主要区别是实体5是面向data add模式，而实体6是面向data in模式。细粒度污点信息流传播中污点属性的行为实体操作及应用条件如表4所示。
表4 细粒度污点信息流传播行为实体操作
细粒度分析条件下控制流传播只包含一种模式，即控制流添加模式control add，随着执行路径的深入，控制流污点信息是一个将当前路径约束逐步添加到全局路径约束的不可逆过程，其行为实体如下：
对比可见，文中所提出的细粒度条件下污点传播策略较粗粒度条件下扩展了模式类别，细化了行为实体。此举既提升了在线模式下污点分析的效率和规模，同时应用离线细粒度污点分析，提高了分析的精准度。
2.5 离线轨迹文件
执行轨迹信息是动态污点分析的基础，污点分析过程中污点属性的获取和传播、污点信息的读取和写入都依赖于执行轨迹信息。在线粗粒度污点分析过程中，执行轨迹信息是通过HOOK机制获取的，包括指令流的提取，内存、寄存器内容读取，可以根据需要实时获取运行时状态信息，信息量足以满足粗粒度污点分析的需要。而细粒度污点分析以包含有限信息的离线轨迹文件为唯一依据，离线轨迹文件信息的完备性和精准性在细粒度污点分析中起了决定性作用。
离线轨迹文件的记录关键在于需求信息的全面性，但完整记录程序运行时的状态信息是不现实的，因此，本文从污点分析的实质出发，以污点为中心，将污点相关作为记录标准，重点执行如表5所示的策略。
表5 污点记录策略
指令运行时状态参数指导行为实体具体执行，同样是污点分析的必要信息。因此，本文的离线轨迹信息文件从污点分析需求出发，着重记录指导污点传播策略制定的污点属性标识、设定污点引入操作的源污点标识、定位污点传播操作的地址信息等，具体结构如表6所示。
表6 离线轨迹文件记录结构
该结构所记录的文件内容都是指令执行前的状态参数，离线分析系统扫描一行轨迹信息后，提取其源污点标识，依据标识有无采用污点标记策略或污点传播策略。获取指令助记符、操作数和污点属性，可确定完整的污点传播策略。提取内容和获取信息的对应关系如表7所示。
表7 离线轨迹文件信息提取
2.6 敏感点检测
污点数据的超权限使用是污点分析检查的重点，本文在粗粒度污点分析模块和细粒度污点分析模块中均设置了敏感点检测，以制定的策略检查污点数据的异常使用。针对当前软件安全的主要威胁点，本文主要对污点数据作为跳转地址、污点数据作为执行代码和污点数据的受控写入等异常以为敏感点。着重检测JMP类、MOV类、CALL、RET指令的污点信息。
本文实现的敏感点检测模式包括：粗粒度敏感点检测(coarse-grained sensitive point detection)，细粒度敏感点检测(fine-grained sensitive point detection)，人工检测(manual- control detection)，3种模式均为可选模式，功能分别为：(1)粗粒度敏感点检测：监控程序运行状态中的异常，防范恶意攻击。(2)细粒度敏感点检测：获取敏感位置污点信息，用于脆弱点验证。(3)人工检测：获取运行时污点状态信息。
3 实验分析
3.1 原型系统构建
本文基于QEMU虚拟机[12]开发实现了粗细粒度结合动态污点分析原型系统。利用虚拟化技术透明地监视目标程序的运行状态，通过HOOK机制监控执行指令、参数及存储状态信息等。基本软/硬件运行环境如表8所示。
表8 实验基本软/硬件环境
原型系统采用前述的框架设计，使用自编译程序test.exe、windows系统自带记事本程序和安装第三方软件Adobe Reader作为测试实例。
3.2 实验过程及分析
在粗粒度污点分析中，将外部引入数据标记为污点源，包括test.exe的输入字符、记事本文件test.txt以及PDF文件test.pdf。使用CTDPS与CTCPS指导污点传播过程，并维护一个共用的污点记录结构，运行过程中依文件记录策略记录离线轨迹文件，具体实例如下：
<7c93017b: IsSource; ADD EAX, [EBX];
REG@EAX[0x00250680]$4T MEM@0x0012fa78 [0x0012fb20] $4T FLAG@EFLAGS[0xffffffa0]$4T>
<7c9301b4: JNZ 0x7c930719; FLAG@EFLAGS[0xfffffcd1] $4T>
<7c872993:CALL 0x7c93069c; REG@0x7c93069c [8ac38ec2]$4N>
监控程序主进程Test.exe、Notepad.exe、AcroRd32.exe，获取并记录其运行指令，提取污点相关指令，同时记录粗粒度污点分析的耗时。表9展示了离线轨迹文件采集过程的统计信息。从实验结果可以看出，随着监控程序的增大和污点数据源的扩大，监控指令数和污点相关指令数均会大幅增加，粗粒度污点分析的耗时也会增加。分析观察数据，发现Adobe Reader 7.0的污点相关指令数占进程相关指令数的比例较大，而其他两者均相对较小。原因在于，test.pdf相对于其他两个输入污点文件，其包含了许多阅读器所需的参数，这些参数和用户写入的PDF文件内容一同被标记为污点数据，同时在文件打开阅读的过程中，被大量使用，故导致污点相关指令数比例的大幅增加。如何筛选污点引入数据，减少污点相关指令数将是笔者下一步工作需要解决的问题。
表9 离线轨迹采集的实验数据
输出离线轨迹文件至离线分析机，通过细粒度污点分析模块进一步进行细粒度污点分析，以FTDPS与FTCPS为指导策略，依次序读取指令流，获取指令参数及存储状态信息，计算并更新内存、寄存器、标志位的污点状态，并将其存储在相应影子内存中。在离线分析过程中，可设置停止位、暂停污点分析、查询污点状态、在离线文件 27 658行查询寄存器EAX、内存地址0x00250680和符号位ZF的污点信息值，结果如下：
line27658EAX:tainted{1,2,3,4,7,8}
line27658 0x00250680:untainted
line27658ZF:tainted{5,6,7,8}
对比粗粒度污点分析污点记录和细粒度污点分析污点查询信息，可以看出污点状态基本一致，但其中也存在个别位置污点属性不统一的情况，主要原因是两者的污点传播策略不一致，粗粒度污点分析以快速方便为目标，相对而言分析的精确度不高，例如有些污点清除策略未制定全面。细粒度分析的策略则相对全面，因此，在具体分析过程中会有些许区别。
在对离线轨迹文件进行细粒度污点分析过程中，本文在表10中记录了细粒度污点分析模块的运行性能。
表10 细粒度污点的分析性能
可以看出，随着应用程序规模的扩大，执行指令数增加，污点分析的耗时也随之增大。细粒度污点分析的主要时间消耗在于：(1)指令条目解析；(2)污点存储模块读写；(3)污点信息集合运算。前两条的耗时与离线轨迹文件中指令数成正比，集合运算耗时与污点源大小关联，所以，细粒度污点分析的耗时与目标软件大小与污点源规模正相关。同时对比该表数据与表9可见细粒度污点分析的耗时和粗粒度污点分析差距不大，在只分析污点相关指令的情况下时间还能进一步缩短，验证了粗细粒度结合的动态污点分析方法具有较高的准确性和快速性。
4 结束语
本文提出一种粗细粒度结合的二进制代码动态污点分析方法，以动态污点分析为基础，重点设计了先粗粒度后细粒度分析的新型框架结构，同时结合分析特性与需求，分别制定了粗细粒度条件下的信息流分析策略，并通过一种松耦合的方式，利用离线轨迹文件来传递分析信息。通过对原型系统的测试，验证了该方法兼有粗粒度和细粒度污点分析的优点，可实现高效、快捷、精确的分析。下一步将研究污点信息的精准化定位和污点传播路径的回溯，提高对大型程序的分析效能。
[1] Lam M S, Martin M C, Livshits V B, et al. Securing Web Applications with Static and Dynamic Information Flow Tracking[C]//Proc. of 2008 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation. New York, USA: ACM Press, 2008: 3-12.
[2] Newsome J, Song D. Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software[C]//Proc. of the 12th Annual Network and Distributed System Security Symposium. San Diego, USA: 2005.
[3] Sharif M, Lanzi A, Giffin J, et al. Automatic Reverse En- gineering of Malware Emulators[C]//Proc. of 2009 IEEE Symposium on Security and Privacy. Oakland, USA: IEEE Press, 2009: 94-109.
[4] Comparetti P M, Wondracek G, Kruegel C, et al. Prospex: Protocol Specification Extraction[C]//Proc. of the 30th IEEE Symposium on Security and Privacy. Washington D. C., USA: IEEE Computer Society, 2009: 110-125.
[5] Yin Heng, Song D, Egele M, et al. Panorama: Capturing System-wide Information Flow for Malware Detection and Analysis[C]//Proc. of ACM Conference on Computer and Communication Security. Alexandria, USA: ACM Press, 2007: 116-127.
[6] Kohli P. Coarse-grained Dynamic Taint Analysis for Defeating Control and Non-control Data[EB/OL]. (2009-06-24). http:// arxiv.org/abs/0906.4481.
[7] Nethercote N, Seward J. How to Shadow Every Byte of Memory Used by a Program[C]//Proc. of the 3rd International ACM SIGPLAN/SIGOPS Conference on Virtual Execution
Environments. San Diego, USA: ACM Press, 2007: 65-74.
[8] Bryant R E. Symbolic Boolean Manipulation with Ordered Binary-decision Diagrams[J]. ACM Computing Surveys, 1992, 24(3): 293-318.
[9] 黄 强, 曾庆凯. 基于信息流策略的污点传播分析及动态验证[J]. 软件学报, 2011, 22(9): 2036-2048.
[10]Denning D E. A Lattice Model of Secure Information Flow[J]. Communications of the ACM, 1976, 19(5): 236-243.
[11]Kang M G, McCamant S, Poosankam P. DTA++: Dynamic Taint Analysis with Targeted Control-Fow Pro- pagation[C]// Proc. of the 18th Annual Network and Distributed System Security Symposium. San Diego, USA: [s. n.], 2011.
[12]Bellard F. Qemu: A Fast and Portable Dynamic Translator[C]// Proc. of USENIX’05. Berkeley, USA: [s. n.], 2005: 41-46.
编辑 金胡考
A Dynamic Taint Analysis Method Combined with Coarse-grained and Fine-grained
SHI Da-wei, YUAN Tian-wei
(Jiangnan Institute of Computing Technology, Wuxi 214083, China)
Combination of coarse-grained and fine-grained Dynamic Taint Analysis(DTA) is developed to take speed and accuracy both into account. By comparing the realization process of coarse-grained DTA and fine-grained DTA, this paper proposes a new analysis framework. It executes online coarse-grained DTA to filter useful instruction, uses offline fine-grained DTA to calculate taint information. Coarse-grained and fine-grained taint mark methods are established respectively by comparing the difference of taint analysis. Data-flow property strategy and control-flow property strategy are developed under the condition of coarse-grained DTA and fine-grained DTA. As a transfer file, offline track record structure is designed to provide necessary information for fine-grained analysis. A prototype system is implemented and the experimental result proves that this method can ensure the rapid collection of taint information through online coarse-grained mode, and use offline fine-grained mode to improve the accuracy with accepted time consumption.
coarse-grained; fine-grained; Dynamic Taint Analysis(DTA); offline track; taint propagation; binary
国家“863”计划基金资助项目(2012AA7111043)。
史大伟(1989－)，男，硕士研究生，主研方向：软件安全；袁天伟，高级工程师。
2013-10-17
2013-11-22 E-mail：sdave@126.com
1000-3428(2014)03-0012-06
A
TP309.2
10.3969/j.issn.1000-3428.2014.03.003
