《基于延后策略的动态多路径分析方法.docx》由会员分享，可在线阅读，更多相关《基于延后策略的动态多路径分析方法.docx（14页珍藏版）》请在三一办公上搜索。
1、基于延后策略的动态多路径分析方法* Supported by the National Natural Science Foundation of China under Grant No. 60703076 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No. 2006AA01Z412, 2007AA01Z451 (国家高技术研究发展计划(863); 作者简介: 陈恺(1982),男,江苏南京人,在读博士,主要研究领域为信息安全，软件漏洞分析与检测，恶意代码分析与防范
2、,email: chenk;冯登国(1965),男,博士,研究员,主要研究领域为密码学与信息安全;苏璞睿(1976),男,博士,副研究员,主要研究领域为信息安全. 陈恺1-3+ 冯登国12 苏璞睿21(信息安全国家重点实验室 中国科学院研究生院, 北京市 100049)2(信息安全国家重点实验室 中国科学院软件研究所, 北京市 100190)3(信息安全共性技术国家工程研究中心，北京市 100190)摘 要:多路径分析是弥补传统动态分析方法的不足，对可执行程序全面分析的重要方法之一。现有多路径方法主要采用随机构造或者根据路径条件构造输入进行路径触发，这两者均存在路径分析不全面和缺乏针对性的问题
3、。本文通过对路径条件分析，确定了检测条件的基本组成元素，提出了弱控制依赖和路径引用集的概念和计算规则，并以此为基础提出一种延后策略的多路径分析方法。在程序分析过程中，对特定的程序检测点和检测点条件，有针对性地进行路径筛选，从语义上进行路径表达式简化，在保证检测点可达和检测表达式具有相同构造形式的前提下，简化检测表达式，减少分析路径的数量。通过对7款恶意软件分析实验，结果表明本方法提高了分析效率和准确性。关键词:多路径分析，可执行程序，漏洞检测，动态分析，延后策略软件分析是检测软件漏洞、软件恶意行为等安全性问题的基础。从分析目标的不同，现有软件分析方法一般分为面向源代码的软件分析和面向可执行程序
4、的软件分析。前者针对有源代码的程序，具有更加丰富的类型信息和结构信息，相对而言，分析准确性更高。但是现有软件多数不提供源代码，尤其是大型的商业软件和进口软件等；同时，即使部分软件提供了源代码，也不能保证使用的可执行程序和源代码之间的对应关系，这一问题在文献1中进行了详细讨论。由于大量的应用软件无法获得源程序，并在一些重要领域应用，直接对其可执行程序进行安全性分析、确保这类软件的安全性显得极为重要，该问题也是国内外研究的热点问题。可执行程序分析方法一般分为静态方法和动态方法两种。静态分析使用反汇编手段，将可执行程序的二进制代码转变为汇编语言并以此为基础进行分析。其优点在于可以较为全面的分析程序代
5、码，但是由于分析过程依赖于大量的推理和符号演算，因此效率较低，且会造成一定数量的误报2，对于一些经过变形和混淆3技术处理的代码也不能很好处理。动态分析方法的基本思想是利用程序运行时的数据提高分析效率和准确性，同时避免由于变形等反静态分析技术带来的不可分析性。传统的动态分析一次只能分析一个运行实例，例如Softice、Ollydbg等，为了提高动态分析的全面性，需要构造执行应用程序的多种可能执行路径，即对可执行程序进行多路径分析。按照动态多路径分析方法的发展，可以将其分为三类。第一类是将可执行程序放在可控环境中（例如调试器等）执行并手动更改分支语句的判断条件进行多路径分析。这类方法需要大量的人工
6、参与，非常繁琐且不具全面性。第二类是自动构造不同的输入，尝试触发程序执行的各种不同路径以暴露出程序潜在的安全问题。这类方法也称为Fuzz方法。虽然此类方法在一定程度上提高了第一类方法的效率和覆盖率，但是大多数情况下，此类方法仅能穷举有限个输入，并不能对所有的输入都进行测试。因此通过此方法验证的程序会有一定数量的漏报，而且会耗费大量时间重复已有测试结果。第三类方法是通过对程序执行过程中的路径条件的求解，有选择地对路径进行分析，较有代表性的如EXE2等。这类方法使用动态分析方式，提高了静态分析的准确性和效率，同时避免了Fuzz方法的随机性，增加了路径选择的效率，本文所做工作也是以此类方法为基础。但
7、是这类方法仍然会产生过多的分析路径，也没有对路径条件进行分析筛选，以至于难以应用到大型程序中4。目前国际上部分学者使用启发式方法尝试减少路径分析数量5，但是效果仍然不理想4。本文所述方法从路径条件与检测点之间关系入手，围绕着条件表达式的组成结构加以展开。我们发现，多路径分析的作用之一在于确定某条语句或若干条语句的集合（称为程序检测点集合）在不同的执行路径下是否满足一定的需求，例如判断某条语句是否存在漏洞或者是否存在恶意行为等。此时在程序分析过程中，部分分支条件的取值并不会影响程序检测点的判断条件，因此产生了条件冗余。针对以上应用场景，本文提出了一种延后策略的可执行程序动态多路径分析方法。与传统
8、多路径分析方法不同，本方法在程序的分支路径选择过程中，并不立即进行路径表达式求解和启用新进程进行多路径分析，而是仅记录分支条件；当遇到程序检测点时，有选择的对部分分支语句进行多路径分析，减少需要分析的路径数量和检测表达式长度，提高了分析效率和准确性。本文主要做了如下贡献：1）对路径执行条件进行分析，确定了检测条件的基本组成元素，提出了弱控制依赖和路径引用集的概念和计算规则，并以此为基础对路径条件进行筛选，简化了检测条件表达式，提高了表达式求解的效率和准确性。2）提出了一种延后策略的多路径分析方法。在动态分析的过程中，并不立即对分支语句进行多路径分析，而是在确定检测点位置和检测条件后，动态分析路
9、径条件，有选择的对检测表达式有控制作用的分支语句进行多路径分析，提高了多路径分析的针对性，简化了多路径构造过程，改进了分析效率。3）实现了一套基于延后策略的多路径分析原型系统。对Perfect Keylogger等7款具有恶意操作的软件进行分析，实验表明，本方法有效简化了检测表达式，避免了无用路径的分析，提高了多路径分析的效率和准确性。本文采用如下组织方式：第1章介绍了目前国内外相关研究工作；第2章讨论了路径条件的组成；第3章提出一种延后的多路径分析方法；第4章进行了实验与分析；最后总结全文。1 相关工作多路径分析是进行程序漏洞检测、程序恶意行为分析的关键方法之一。目前国际上对可执行程序进行多
10、路径分析一般可以分为静态分析和动态分析两种方式。静态分析方法多在静态反汇编程序的基础上，提出相关的分析方法进行程序分析。在反汇编方面，目前已有较为成熟的方法和工具，例如IDA Pro IDA Pro Disassembler - multi-processor, windows hosted disassembler and debugger, 等。Wisconsin大学的WiSA项目组在可执行程序的静态分析方面做了大量的工作，提出了分析可执行程序的VSA6方法，并开发出CodeSurfer/x867等工具。在反汇编的基础上进行符号执行，可以对程序进行多路径分析8, 9。国内如夏一民等人在对漏
11、洞进行检测时，提出了基于条件约束的方法10，此方法也可应用在多路径分析上。静态分析虽然可以较为全面的分析程序代码，但是由于缺乏程序运行时的数据信息，所以分析效率较低，且会造成一定数量的误报2。对于一些经过变形和混淆3技术处理的代码，静态分析也难以处理。目前，人们使用一些基础理论方法，例如切片方法11，试图提高静态分析的准确性，但效果仍然不理想12。动态多路径分析是目前重要的多路径分析方法。最初人们为了触发程序的不同路径，尽量多的构造出不同的输入，这类方法称为Fuzz方法。较有代表性的是Ghosh13，它将程序看作是黑盒，通过变换不同的输入，观察程序是否会出现异常，从而进行漏洞查找。这类方式不需
12、要对程序进行分析，而是对程序进行测试，所以执行速度较快。但是大多数情况下，此类方法仅能穷举有限个输入，并不能对所有的输入都进行测试，因此通过此方法验证程序会存在一定数量的漏报。同时，这类方法效率很低，例如程序中有分支语句x=10，这类方法要对x进行232计算才能对不同分支进行处理。之后人们通过对执行路径条件进行分析，产生了白盒Fuzz的方法。白盒Fuzz方法对不同的分支条件求解，计算出可能的输入并尽量多的对不同分支进行多路径分析，较有代表性的是EXE2 、Moser14和SAGE1。但是这类方法需要对遇到的每一个依赖于外部输入的分支都进行多路径分析，因此很大程度上影响了实现效率。Godefro
13、id使用了语法指导的Fuzz分析15，但是预先对缺乏源代码的可执行程序输入部分进行语法分析非常困难且准确性不高，同时这种方法仍然会产生较多的无用路径。多种启发式方法5, 16, 17也被提出进行路径选择，试图在尽量短的时间内达到更多的代码覆盖率，但是这类方法仅是从搜索策略的角度入手，例如深度优先、广度优先、随机法或通过一定的算子计算出路径上的权值来进行路径选择，没有对路径本身的语句进行分析和优化处理，因此效果仍然不够理想4。RWSet方法对指令引用集合和定义集合进行分析，从程序语义上尝试减少多路径分析的数量，具有一定效果4，但是它仅是从程序节点的数值依赖角度进行分析，没有对控制依赖进行分析，例
14、如缺乏针对程序检测点的运行条件分析，和对条件路径叠加的处理，因此仍然存在无用路径；且仅适用于源代码分析。现有多路径分析方法中，路径分析不全面和分析过多无用路径的问题影响了分析的准确性和分析效率。其原因体现在以下两个方面：1）对条件路径不加选择地进行多路径扩展。在程序执行过程中，遇到分支语句即对路径进行分解，进而对每个分支路径分别产生一个新进程进行计算。Cadar2等人在此基础上对动态依赖于外部输入的分支语句进行路径分解，以减少路径数目，但是这类方法仍然会产生较多的无用路径。2）路径表达式过长以至无法求解。在分支计算过程中，为了明确程序的执行路径，需要记录下分支条件，当分支数目增加时，条件表达式
15、长度也随之增加。条件表达式的数目和长度的增加，使得对程序进行多路径分析的难度显著增加，甚至在有限时间内不可求解。这也是造成路径分析不全面的原因之一。本文针对以上问题，对程序检测点与路径条件的关系进行分析，确定了路径条件的组成，提出一种延后分析的策略。2 路径条件的组成本章以一示例为引, 说明路径条件的必要性和分支选择的时机问题，并定义相关概念和具体的计算规则。图1.a是一个典型的分支流程。假设节点1是分支语句，其两个出口分别指向节点2和节点3，节点4是后必经节点。节点1的入口条件是C，两个分支条件为e和。 图1.a分支语句图1.b循环语句图1.c子程序调用语句现有多路径分析方法在程序运行时，会
16、记录程序运行过程中所有不能静态确定分支方向的条件集合CE。例如图1.a中，假设条件e依赖于外部输入，表示为，且。当程序运行至节点1进行分支选择时，运行条件会变为或，且会在节点1处产生新的进程进行多路径分析。假设检测点在节点2或3时，以上分析过程是没有冗余的，因为条件e或保证了检测点的运行条件。但若检测点在节点4处，条件e和的必要性并不明显，因为它们并未保证此时程序的运行条件。因此，需要对节点2、3、4中引用变量集和定义变量集进行更深入的分析方可确定条件e或的必要性。易知，对于理论上最小路径条件集CE，有。对于循环语句（图1.b）与子程序调用语句（图1.c），以上情况均会出现。因此正确选择分支条
17、件，可以减少分支的数目和路径表达式的长度，也避免产生无用的进程进行多路径分析。定义1（路径） 路径P是若干条顺序执行的语句组成的序列，记为：。用表示所有以l0为起点，以ln为终点的路径。用表示所有以l0后继节点为起点，以ln为终点的路径，用表示所有以l0起点，以ln前驱节点为终点的路径。对于特定的P，使用表示路径长度。定义2（条件路径）条件路径CP是路径P中顺序执行的分支语句组成的序列，记为，其中c1是程序执行路径上第一个分支语句。易知，。用表示所有以l0为起点，以ln为终点的条件路径。用表示所有以l0后继节点为起点，以ln为终点的条件路径，用表示所有以l0起点，以ln前驱节点为终点的条件路径
18、。对于特定的CP，使用表示条件路径长度。定义3（检测条件）检测条件指在程序运行至检测点p位置时，进行某些预定义检查所需的条件，例如判断当前状态是否会出现漏洞的条件等，用CCp表示。定义4（检测表达式）对于程序执行路径P上的结点l，程序检测表达式。其中C保证程序在每次执行过程中均可到达l，且CCl具有相同的符号表示。在不发生歧意的情况下，将简记为。定理1. 。证明：由检测表达式的定义易证。证毕。定义5（弱控制依赖）在路径上，对于条件结点lk及任意后续结点lj（），假设lk的后必经结点为lm，若，则称lj弱控制依赖于lk，记为。根据弱控制依赖的定义可知其与控制依赖的关系：，其中表示lj控制依赖于l
19、k，但反之不然。定义6（运行条件）在条件执行路径上，对于检测点p，如果，则称条件ci是检测点p的运行条件。用RCp表示检测点p运行条件的集合。定理2. 。证明：由运行条件的定义，可知p不是ci的后必经节点，因此存在路径，其中ln是结束语句，使得。如果，则不能保证程序运行到节点p处，且无法在p点进行表达式检测，所以定理2得证。证毕。在图1.a中，如果在节点2处进行检测，有，根据定理2，有。定理2是条件语句是否属于程序检测表达式的充分条件，但不是必要条件，因此对于检测点p，当时，无法确定ci是否属于CEp。例如图1.a中，如果在节点4处进行检验时，将无法确定是否将e或者放入CE4。此时，需要进一步
20、分析程序运行过程中定义的变量集和引用的变量集。引理1. 在条件执行路径上，假设l是分支节点ci的第一个后必经节点，有，其中USE(C)表示表达式C的引用集合，DEF(C)表示表达式C的定义集合，表示在p路径上V集合的变量值。证明：根据题设条件，对于程序的执行路径，存在不同的路径且，在程序的两次执行过程中，当ci取不同分支时，即l处USE(CCl)的值不同，因此为了保证在l处CEl中USE(CCl)具有相同值，需要将ci加入CEl。证毕。考虑到在不同路径上Vp和Vp具有相同值，在多路径分析时，添加上条件ci也不会影响CEl的解集，而且多数情况下编译器会将不同路径上具有相同变量赋值的语句提取出进行
21、优化，因此引理1可以简化为定理3。定理3. 在条件执行路径上，假设l是分支节点ci的第一个后必经节点，则。定理3仅针对分支语句的第一个后必经节点l进行计算，并未考虑l后续节点的条件依赖关系。假设分支语句ci的第一个后必经节点是l1，检测语句为l1之后的语句l2，且，则需要考虑中变量定义集合与之间的关系。定义7（路径引用集）在程序路径上，对于在语句l中使用的变量集合s，s依赖于路径P外的变量集合称为变量集合s在路径P上的路径引用集，用USE(P, s, l)表示。根据路径引用集的定义，可以获得USE(P, s, l)的计算方法。对于所有,这里使用推导规则方式：空语句推导规则：单语句推导规则：多语
22、句推导规则：多路径推导规则：其中，表示当条件c成立时，选择x1，否则选择x2。定义8（值依赖条件）在条件执行路径上，假设lj是分支节点ci的第一个后必经节点，对于检测点为lk，如果，则称条件ci是检测点lk的值依赖条件。用表示检测点l值依赖条件的集合。定理4. 在条件执行路径上，对于检测点l，有。证明：因为，根据值依赖条件的定义，存在ci的后必经节点l，使得。当时，由空语句推导规则，有，根据定理3，可知。当时，在路径上由路径引用集的推导规则，可以求得集合，不妨将s看作，根据定理3，可知。证毕。定理4描述了在程序条件路径CP上，对于和检测点l，当时，是否将ci加入l点的检测表达式的充分条件。至此
23、，我们可以得到对于任意条件ci，有如下定理。定理5. 在程序执行路径P上，对于检测点l，有。证明：由检测表达式的定义，有，充分性得证。根据定理1、定理2和定理4，有，必要性得证。因此。证毕。3 延后的多路径分析方法现在多路径分析方法，一般是在分支语句处判断当前分支条件c，如果（其中DD表示数据依赖），则创建两个进程，分别执行并递归的进行多路径分析2。当过多分支语句或者循环控制语句依赖于外部输入时，这类多路径分析方法会因为创建的分析进程数量过多而不实用（与分支数目成指数关系），这也是目前多路径分析方法难以应用于大规模程序的主要原因之一。由定理5，在程序执行过程中，对于条件，若，则表示c取值真假与
24、CCl无关，因此不需要在条件c处进行多路径扩展。这里提出一种基于延后策略的多路径分析方法，针对已有的检测点，确定与检测点相关的分支语句。此方法由两种模式组成：监控模式和检测模式。在监控模式下，被分析程序正常运行，监控程序记录路径P、条件路径CP等相关的信息。检测模式指遇到程序检测点l后，判断条件与间关系的过程。程序开始时以监控模式进行。每当遇到指令I时，如果I是程序检测点，则转入检测模式，否则将I加入执行路径P。如果I是分支语句，且，则将I加入条件路径CP。使用切片方法可以判断I是否依赖于外部输入，但其效率较低，且不准确。这里我们使用污点传播方式判断I是否依赖于外部输入。污点传播18是一种有效
25、确认变量之间是否相关的分析方法。通过设置污点源和定义污点传播规则，可以判断程序运行过程中变量是否与污点源相关。污点源可以设置为外部文件、键盘输入和网络输入等。表1是部分指令的污点传播规则，包括数据转移类指令、算术操作指令、逻辑操作类指令、比较类指令等。为了能够更快的确定某块内存区域是否依赖于外部输入，我们使用了影子内存的方法。影子内存为真实内存的镜像，其每块内存空间表示相对应的真实内存是否依赖于外部输入。为了保持分析过程中的连贯性，我们对寄存器也实现了相应的影子机制。表1. 污点传播规则指令分类传播规则示例语句数据转移指令T(op1)T (op2)mov op1, op2算术操作指令T (op
26、1)T (op1)T(op2); T (add, PSW)T (op1)T(op2)add op1, op2逻辑操作指令T (op1)T (op1)T(op2); T(and, PSW)T (op1)T(op2)and op1, op2比较类指令T(cmp, PSW)T (op1)T(op2)cmp op1, op2其中T(op)BOOL，表示op所指向的操作数是否为污点数据；PSW表示机器状态字；(op, PSW)，表示op操作引发PSW中变化的位置，例如add操作会引起C、P、A、Z、S、O等标志位的改变。注意add、and等算术/逻辑指令会影响PSW的值，这里也必须引入，因为jne等跳转
27、指令依赖于PSW的值。由于缺少源代码，污点传播在分析过程中存在一定的局限性，主要包括如下几条：(1) 嵌套循环难以处理的问题：目前原型系统中我们采取的措施是将循环展开19，但这样会造成需要多路径分析的分支数量过多的问题。在未来的工作过程中，我们将重点对循环进行处理，进一步减少循环对多路径分析的影响。(2)操作指令集不完备的问题：由于CPU指令较多，目前的原型系统中完成了数据传输类指令、算数操作类指令、逻辑操作类指令和比较类指令等指令集合的污点传播分析，对于特殊的指令，例如MMX指令、FPU指令等并没有完成污点传播分析，这可能会造成分析不全面的问题。同时我们仅支持Intel CPU的指令集，并不
28、兼容其他类型的CPU。在未来的工作中，我们将支持更多的指令集，以便完善我们的原型系统。(3)系统调用的问题: 目前原型系统仅在用户层进行分析，并没有对内核层进行污点传播处理。这可能会造成部分污点传播失效的问题，使得分析的全面性受阻。目前采用国际上使用较多的方式，对系统调用总结出“摘要”（Summary）信息20，即对部分系统调用增加一定程度的信息以保持污点传播分析的连续性。目前我们对NtReadFile等系统调用增加了“摘要”信息。在目前软件安全逆向分析中，单一节点的检测往往不能作为漏洞点存在的依据，因此需要考虑多个检测点间的共同作用。假设需要共同作用的检测点集合为，当程序运行至L时，进入检测
29、模式。CP中记录了执行路径P上遇到的所有依赖于外部输入的条件。不妨设。此时需要逐个判断CP中的条件c是否属于CEL。由定理5，所以需判断条件c是否属于集合。定义函数表示结点b是否是结点a的后必经结点，如果是，则返回true，否则返回false。对于路径，其中l是L中执行流程序列的最后一条语句。从指令li开始逆序进行分析。对于第一条指令li，根据不同情况：(1) ：，且由于，因此，即，根据定理2，将li加入CEl，用表示。若，更新路径引用集。继续分析li-1。(2) ：使用路径引用集的推导规则计算的路径引用集，即计算，其中。若，则。当时，如果，根据定理3可知，。按此步骤继续分析li-1。对于任意
30、，根据如下方法分析：(1) ，(i) 若，更新路径引用集；(ii) 若，则，根据定理2，并更新路径引用集。若，更新路径引用集。继续分析lj-1。(2) ：使用路径引用集的推导规则，计算的路径引用集，即，其中在分析指令时计算出。若，更新路径引用集。当时，如果 ，根据定理5可知，。继续分析lj-1。算法1是程序执行与检测表达式生成的算法框架。目前原型系统的实现对于分支路径采用动静结合方式判断相关的引用集合和定义集合，没有对alias21问题进行分析。如果发现某分支语句的分析过程中，有不确定目标的alias操作，则将当前分支条件加入相应检测点的值依赖条件VDC中，因此可能会造成VDC偏大，但此方法不
31、会失去准确性。实验结果表明，即使使用这种方式，计算出的需多路径分析的条件数量仍然小于EXE方式下的相应条件数量。在今后的工作中，可以使用更精确的方法对alias问题进行分析，进一步减少分支数目。在程序循环时，路径减少显得尤为明显。下例是在循环程序的示例，对比了EXE方法和延后方法的不同处理方式。例1. 检测点与循环：int m=input;/ 表示m依赖于外部输入int n=input; / 假设n20int a20; int k = 0;if(n 20)i: for ( int i = 0; i n; i+)k = i; / 没有定义m，但是定义了kj: am = k; / 检测语句，检测条
32、件是0m20 对于以上代码片段，假设检测点是j，检测条件是0m20。如果使用EXE的处理方式，在i处，需要分别对n=0、n=1、n=19进行多路径分析。但是对于这种方式中的每一条路径，程序到达检测点j的检测条件均没有变化，仍然为0m20。因此在i处对n进行多路径分析是没有必要的。但使用延后分析方法，不需要在i处进行多路径分析，因此有效节省了计算资源。4 实验与分析为了测试本方法的有效性和性能，我们实现了延后策略多路径分析的原型系统。原型系统由四部分组成，分别是加载模块、执行模块、污点传播模块和延后分析模块。加载模块首先加载被分析的程序，再由执行模块执行，执行的基本单位为程序语句，每执行完一条语
33、句后由污点传播模块进行污点源的识别与污点数据传播，之后进行延后策略的分析。分析过程中使用缓存技术进行优化，当后续程序运行时使用到已分析过的结果时，直接取缓存结果即可。整个系统使用C+语言实现，约1万行代码。计算机硬件使用Dell Optiplex 360计算机，配以Intel Core 2 Duo CPU E7300 2.66GHz CPU，2GB内存，操作系统使用Windows XP SP3。多路径研究的意义在于其进行软件安全漏洞检测、程序异常行为分析方面的贡献。因此我们使用实际案例数据测试基于延后方法动态多路径分析的有效性。Win32.NetSky是2004年传播最广泛的蠕虫之一, 它在W
34、indows环境下以邮件方式进行传播。在我们的分析过程中，将GetLocalTime返回值作为污点数据，并以此为污点源进行分析。使用随机的日期，程序流程以下图中最上一层的调用序列到达0x100025EE。此时路径上的分支语句有0x100025A3、0x100025AD、0x100025BA、0x100025C3、0x100025CB、0x100025D3、0x100025DC，其中0x100025AD与污点数据无关。EXE2方法与Moser14方法应用广泛，是目前国际上最有代表性的可执行程序多路径分析方法之一。由于Moser方法原理与EXE方法类似，实验时仅将延后方法与EXE方法作对比。使用E
35、XE方法多路径分析时，需要在除0x100025AD外的其他分支语句处启用新的进程进行路径分析；若使用延后策略的方法，可以发现0x100025A3、0x100025CB、0x100025D3、0x100025DC不属于0x100025EE的运行条件或值依赖条件，因此不必在这些位置进行多路径扩展，仅需在0x100025BA和0x100025C3处进行多路径分析即可，提高了整体分析的效率。实际分析时，在0x100025BA处进行多路径扩展将到达NetSky程序的攻击处ATTACK。图2 NetSky多路径分析图为了对比EXE方法和延后方法对于不同程序需要多路径分析的分支数量，我们对7款恶意软件进行测
36、试。Perfect Keylogger是一款记录键盘操作的软件；CodeRed、Nimda、Slammer、Maslan为网络蠕虫；QQ Thief和ExploitIE是黑客工具。表2记录了各程序在运行过程中相应检测表达式中条件数量的平均值。多路径分析针对不同的目标，检测点的选取是不同的，这里不考虑具体的分析目标，具体检测点的选取不是本论文的讨论重点。目前国际上对程序检测点有多种选取方法22，为了不失一般性，本文采用在程序中的随机检测点进行分析。检测点的产生规则是在程序启动后，每100条指令基本块为间隔作为一个程序检测点，各程序产生的检测点的数目随着程序的不同而不同。多路径分析过程中，创建新进
37、程的数量与条件数量成指数关系，因此条件数量在一定程度上反映多路径分析效率以及路径求解的效率。在程序运行过程中，检测表达式中条件数量会不断变化，因此如果简单的对每个检测表达式中的条件数量进行平均，将会丧失结果的准确性。这里以原始(Origin)方法为基础，对每个检测点在各种方法下的条件表达式数量进行归一化，最后取平均值，比较EXE方法和延后策略(LA)对表达式长度的缩减。其中原始方法指对路径条件不做任何判断均进行记录。表2中第2列表示分析过程中，程序检测点总数；Origin表示原始方法，这也是归一化处理的基础；第3列为使用EXE方法缩减后的条件表达式长度所占Origin方法的比例；第4列是使用延
38、后策略的条件数量相对于Origin方法所占比例；最后一列以百分制表示延后策略检测表达式条件数量占EXE方法的比例。从表1中可以看出，EXE方法虽然使用了污点传播进行处理，但仍存在大量无用条件。使用延后策略的方法能够减少大量的无用分支语句，简化了检测表达式，减少了分支的数量，其条件数量平均仅占EXE方法的22.97%。表2. 三种多路径方法的比较程序名称检测点数量EXE/ OriginLA/ OriginLA/EXE(%)Perfect Keylogger31930.16660.025615.37CodeRed15770.17670.038121.56Nimda15050.07090.00801
39、1.28Slammer13630.15620.033621.51Maslan12340.05720.00142.45QQ Thief12310.01710.008348.54ExploitIE12230.02170.008740.09表2从整体上对比了EXE方法和延后方法之间对不同程序检测点中条件数量的差异，但并没有显示出在分析过程中，检测点条件数量的变化情况。图3以Perfect Keylogger为例，从程序随时间执行的角度加以说明。图中横轴记录的是程序顺序流程中随机选取的不同检测点，纵轴表示检测表达式中条件的数目。由图中可知，使用EXE方法，程序的条件检测点数目随程序的执行几乎呈线性增长
40、，当程序执行流程越长，检测表达式中条件数量越多。值得注意的是，条件数量每增加1，产生的进程数量并不是增加1，而是在原有基础上增加1倍，即进程数量与条件表达式的数量之间为指数关系。因此这也是EXE方法难以分析大型程序的原因。从图中看出，采用延后策略的方法，检测点条件数量呈锯齿形分布。其原因是检测表达式中条件数量与程序的执行过程的长短并无直接关系，仅与变量之间的依赖关系和运行条件相关。由于程序中外界变量仅影响部分程序语句，随着程序的执行，此外界变量可能不被继续使用，因此后续阶段的检测表达式中的检测条件与前一阶段可能并不相关，这也是图中曲线呈锯齿型分布的原因。因此，本方法更适用于大型程序。 图3 P
41、erfect Keylogger中EXE方法和LA方法对于不同检测点条件数量的时间流程图图4 分析过程中各程序影子内存数量由于影子内存需与真实内存保持对应关系，因此在分析过程中可能会占用较大空间。在本原型系统中，采用实时记录的影子内存方法。当有新的内存空间被申请时，增加相应的影子内存；当目标进程对应的内存空间被释放时，影子内存也随之释放。所以原型系统不需要使用整个内存空间作为影子内存，而仅仅需要动态维护内存堆栈即可，更大程度地减少了原型系统的内存空间占用量。为了确认分析过程中内存占用情况，我们对影子内存进行了分析。图4是在分析过程中各程序影子内存占用内存空间的最大值（单位是KB）。从图中可知，
42、本原型系统使用影子内存机制所占的内存空间（包括堆栈）不超过15M，平均内存占用率仅为6.47MB。由于因此，本系统具有较高的空间利用率。为了测试延后方法中检测点数量对检测表达式条件筛选的效率影响，表3对比了在延后策略下，当检测点数量发生变化时，筛选表达式条件所需的时间。仍然对7款恶意软件进行测试，检测点数量选取0、10、100、1000个，时间单位为秒。从表中可知，使用延后方法分析10个、100个检测点，相对于0个检测点并没有在时间效率上减小许多。即使分析1000个检测点，增加的额外检测时间也与检测点数量几乎呈线性关系。因此延后方法具有一定的时间效率。从表中可以看出，对于部分软件，例如Nimd
43、a、QQ Thief等，即使在1000个检测点时分析时间仍然较少。这是由于算法在分析过程中，对部分中间过程的运算结果（例如后必经结点的计算结果）进行保留，并在下次运算时直接使用造成的。表3. 各种方法运行时间比较（单位：秒）程序名称LA(0)LA(10)LA(100)LA(1000)Perfect Keylogger191195208313CodeRed535668149Nimda118130134162Slammer515664217Maslan606165106QQ Thief574585636759ExploitIE2872923285795 结论现有多路径分析方法主要存在路径分析不全面
44、、分析效率较低、分析过程中存在大量无用路径等问题。部分工作仅从检测表达式本身对路径表达式进行优化求解，但并没有结合程序检测点和路径条件进行深入简化。本文针对以上问题，提出了弱控制依赖和路径引用集的概念以及相应的计算规则，并在此基础上提出了一种延后策略的可执行程序动态多路径分析方法。在程序分析过程中，不立即进行路径表达式求解和多进程构造，而是记录当前的分支条件。当遇到程序检测点时，有针对性的根据检测点条件进行路径筛选，从语义上进行路径表达式简化，减少需要分析的路径数量，简化检测表达式。本文实现了一套原型系统，并对Perfect Keylogger等7款恶意软件进行分析实验，结果表明本方法提高了多
45、路径分析效率和准确性。实验中发现，在循环处理过程中，会产生大量的条件表达式，如何对这类条件进行有效简化是未来的工作方向之一。同时，结合现有漏洞检测方法，对程序检测点进行更细粒度的选择，更多的支持污点分析的指令数量和完善系统调用信息，进行程序安全性分析也是本文未来的工作方向。References:1Godefroid P., Levin M. Y., and Molnar D., Automated whitebox fuzz testing, /Network and Distributed System Security Symposium, San Diego, CA, 2008. The
46、 Internet Society,2008.2Cadar C., Ganesh V., Pawlowski P. M., Dill D. L., and Engler D. R., EXE: automatically generating inputs of death, /13th ACM conference on computer and communications security, Alexandria, VA, U.S.A, 2006. New York, NY, USA:ACM Press, 2006: 322-335.3Linn C. and Debray S., Obf
47、uscation of executable code to improve resistance to static disassembly, /10th ACM conference on Computer and communications security, Washington D.C., USA, 2003. New York, NY, USA:ACM Press, 2003: 290-299.4Boonstoppel P., Cadar C., and Engler D., RWset: attacking path explosion in constraint-based test generation, /14th International Conference, TACAS, Budapest, Hungary, 2008. New York: Springer-Verlag, 2008: 351-366.5Xie T., Tillmann N., de Halleux J., and Schulte W., Fitness-guided p
