基于延后策略的动态多路径分析方法

《计算机学报》2010年第3期，2010，33（3）基于延后策略的动态多路径分析方法陈恺1-3+冯登国12苏璞睿21(信息安全国家重点实验室中国科学院研究生院,北京市100049)2(信息安全国家重点实验室中国科学院软件研究所,北京市100190)3(信息安全共性技术国家工程研究中心，北京市100190)摘要:多路径分析是弥补传统动态分析方法的不足，对可执行程序全面分析的重要方法之一。现有多路径方法主要采用随机构造或者根据路径条件构造输入进行路径触发，这两者均存在路径分析不全面和缺乏针对性的问题。本文通过对路径条件分析，确定了检测条件的基本组成元素，提出了弱控制依赖和路径引用集的概念和计算规则，并以此为基础提出一种延后策略的多路径分析方法。在程序分析过程中，对特定的程序检测点和检测点条件，有针对性地进行路径筛选，从语义上进行路径表达式简化，在保证检测点可达和检测表达式具有相同构造形式的前提下，简化检测表达式，减少分析路径的数量。通过对7款恶意软件分析实验，结果表明本方法提高了分析效率和准确性。关键词:多路径分析，可执行程序，漏洞检测，动态分析，延后策略软件分析是检测软件漏洞、软件恶意行为等安全性问题的基础。从分析目标的不同，现有软件分析方法一般分为面向源代码的软件分析和面向可执行程序的软件分析。前者针对有源代码的程序，具有更加丰富的类型信息和结构信息，相对而言，分析准确性更高。但是现有软件多数不提供源代码，尤其是大型的商业软件和进口软件等；同时，即使部分软件提供了源代码，也不能保证使用的可执行程序和源代码之间的对应关系，这一问题在文献[1]中进行了详细讨论。由于大量的应用软件无法获得源程序，并在一些重要领域应用，直接对其可执行程序进行安全性分析、确保这类软件的安全性显得极为重要，该问题也是国内外研究的热点问题。可执行程序分析方法一般分为静态方法和动态方法两种。静态分析使用反汇编手段，将可执行程序的二进制代码转变为汇编语言并以此为基础进行分析。其优点在于可以较为全面的分析程序代码，但是由于分析过程依赖于大量的推理和符号演算，因此效率较低，且会造成一定数量的误报[2]，对于一些经过变形和混淆[3]技术处理的代码也不能很好处理。动态分析方法的基本思想是利用程序运行时的数据提高分析效率和准确性，同时避免由于变形等反静态分析技术带来的不可分析性。传统的动态分析一次只能分析一个运行实例，例如Softice、Ollydbg等，为了提高动态分析的全面性，需要构造执行应用程序的多种可能执行路径，即对可执行程序进行多路径分析。按照动态多路径分析方法的发展，可以将其分为三类。第一类是将可执行程序放在可控环境中（例如调试器等）执行并手动更改分支语句的判断条件进行多路径分析。这类方法需要大量的人工参与，非常繁琐且不具全面性。第二类是自动构造不同的输入，尝试触发程序执行的各种不同路径以暴露出程序潜在的安全问题。这类方法也称为Fuzz方法。虽然此类方法在一定程度上提高了第一类方法的效率和覆盖率，但是大多数情况下，此类方法仅能穷举有限个输入，并不能对所有的输入都进行测试。因此通过此方法验证的程序会有一定数量的漏报，而且会耗费大量时间重复已有测试结果。第三类方法是通过对程序执行过程中的路径条件的求解，有选择地对路径进行分析，较有代表性的如EXE[2]等。这类方法使用动态分析方式，提高了静态分析的准确性和效率，同时避免了Fuzz方法的随机性，增加了路径选择的效率，本文所做工作也是以此类方法为基础。但是这类方法仍然会产生过多的分析路径，也没有对路径条件进行分析筛选，以至于难以应用到大型程序中[4]。目前国际上部分学者使用启发式方法尝试减少路径分析数量[5]，但是效果仍然不理想[4]。本文所述方法从路径条件与检测点之间关系入手，围绕着条件表达式的组成结构加以展开。我们发现，多路径分析的作用之一在于确定某条语句或若干条语句的集合（称为程序检测点集合）在不SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60703076(国家自然科学基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2006AA01Z412,2007AA01Z451(国家高技术研究发展计划(863));作者简介:陈恺(1982－),男,江苏南京人,在读博士,主要研究领域为信息安全，软件漏洞分析与检测，恶意代码分析与防范,email:[e-mail];冯登国(1965－),男,博士,研究员,主要研究领域为密码学与信息安全;苏璞睿(1976－),男,博士,副研究员,主要研究领域为信息安全.22同的执行路径下是否满足一定的需求，例如判断某条语句是否存在漏洞或者是否存在恶意行为等。此时在程序分析过程中，部分分支条件的取值并不会影响程序检测点的判断条件，因此产生了条件冗余。针对以上应用场景，本文提出了一种延后策略的可执行程序动态多路径分析方法。与传统多路径分析方法不同，本方法在程序的分支路径选择过程中，并不立即进行路径表达式求解和启用新进程进行多路径分析，而是仅记录分支条件；当遇到程序检测点时，有选择的对部分分支语句进行多路径分析，减少需要分析的路径数量和检测表达式长度，提高了分析效率和准确性。本文主要做了如下贡献：1）对路径执行条件进行分析，确定了检测条件的基本组成元素，提出了弱控制依赖和路径引用集的概念和计算规则，并以此为基础对路径条件进行筛选，简化了检测条件表达式，提高了表达式求解的效率和准确性。2）提出了一种延后策略的多路径分析方法。在动态分析的过程中，并不立即对分支语句进行多路径分析，而是在确定检测点位置和检测条件后，动态分析路径条件，有选择的对检测表达式有控制作用的分支语句进行多路径分析，提高了多路径分析的针对性，简化了多路径构造过程，改进了分析效率。3）实现了一套基于延后策略的多路径分析原型系统。对PerfectKeylogger等7款具有恶意操作的软件进行分析，实验表明，本方法有效简化了检测表达式，避免了无用路径的分析，提高了多路径分析的效率和准确性。本文采用如下组织方式：第1章介绍了目前国内外相关研究工作；第2章讨论了路径条件的组成；第3章提出一种延后的多路径分析方法；第4章进行了实验与分析；最后总结全文。1相关工作多路径分析是进行程序漏洞检测、程序恶意行为分析的关键方法之一。目前国际上对可执行程序进行多路径分析一般可以分为静态分析和动态分析两种方式。静态分析方法多在静态反汇编程序的基础上，提出相关的分析方法进行程序分析。在反汇编方面，目前已有较为成熟的方法和工具，例如IDAPro①等。Wisconsin大学的WiSA项目组在可执行程序的静态分析方面做了大量的工作，提出了分析可执行程序的VSA[6]方法，并开发出CodeSurfer/x86[7]等工具。在反汇编的基础上进行符号执行，可以对程序进行多路径分析[8,9]。国内如夏一民等人在对漏洞进行检测时，提出了基于条件约束的方法[10]，此方法也可应用在多路径分析上。静态分析虽然可以较为全面的分析程序代码，但是由于缺乏程序运行时的数据信息，所以分析效率较低，且会造成一定数量的误报[2]。对于一些经过变形和混淆[3]技术处理的代码，静态分析也难以处理。目前，人们使用一些基础理论方法，例如切片方法[11]，试图提高静态分析的准确性，但效果仍然不理想[12]。动态多路径分析是目前重要的多路径分析方法。最初人们为了触发程序的不同路径，尽量多的构造出不同的输入，这类方法称为Fuzz方法。较有代表性的是Ghosh[13]，它将程序看作是黑盒，通过变换不同的输入，观察程序是否会出现异常，从而进行漏洞查找。这类方式不需要对程序进行分析，而是对程序进行测试，所以执行速度较快。但是大多数情况下，此类方法仅能穷举有限个输入，并不能对所有的输入都进行测试，因此通过此方法验证程序会存在一定数量的漏报。同时，这类方法效率很低，例如程序中有分支语句x=10，这类方法要对x进行232计算才能对不同分支进行处理。之后人们通过对执行路径条件进行分析，产生了白盒Fuzz的方法。白盒Fuzz方法对不同的分支条件求解，计算出可能的输入并尽量多的对不同分支进行多路径分析，较有代表性的是EXE[2]、Moser[14]和SAGE[1]。但是这类方法需要对遇到的每一个依赖于外部输入的分支都进行多路径分析，因此很大程度上影响了实现效率。Godefroid使用了语法指导的Fuzz分析[15]，但是预先对缺乏源代码的可执行程序输入部分进行语法分析非常困难且准确性不高，同时这种方法仍然会产生较多的无用路径。多种启发式方法[5,16,17]也被提出进行路径选择，试图在尽量短的时间内达到更多的代码覆盖率，但是这类方法仅是从搜索策略的角度入手，例如深度优先、广度优先、随机法或通过一定的算子计算出路径上的权值来进行路径选择，没有对路径本身的语句进行分析和优化处理，因此效果仍然不够理想[4]。RWSet方法对指令引用集合和定义集合进行分析，从程序语义上尝试减少多路径分析的数量，具有一定效果[4]，但是它仅是从程序节点的数值依赖角度进行分析，没有对控制依赖进行分析，例如缺乏针对程序检测点的运行条件分析，和对条件路径叠加的处理，因此仍然存在无用路径；且仅适用于源代码分析。①IDAProDisassembler-multi-processor,windowshosteddisassembleranddebugger,陈恺等:基于延后策略的动态多路径分析方法33现有多路径分析方法中，路径分析不全面和分析过多无用路径的问题影响了分析的准确性和分析效率。其原因体现在以下两个方面：1）对条件路径不加选择地进行多路径扩展。在程序执行过程中，遇到分支语句即对路径进行分解，进而对每个分支路径分别产生一个新进程进行计算。Cadar[2]等人在此基础上对动态依赖于外部输入的分支语句进行路径分解，以减少路径数目，但是这类方法仍然会产生较多的无用路径。2）路径表达式过长以至无法求解。在分支计算过程中，为了明确程序的执行路径，需要记录下分支条件，当分支数目增加时，条件表达式长度也随之增加。条件表达式的数目和长度的增加，使得对程序进行多路径分析的难度显著增加，甚至在有限时间内不可求解。这也是造成路径分析不全面的原因之一。本文针对以上问题，对程序检测点与路径条件的关系进行分析，确定了路径条件的组成，提出一种延后分析的策略。2路径条件的组成本章以一示例为引,说明路径条件的必要性和分支选择的时机问题，并定义相关概念和具体的计算规则。图1.a是一个典型的分支流程。假设节点1是分支语句，其两个出口分别指向节点2和节点3，节点4是后必经节点。节点1的入口条件是C，两个分支条件为e和e。1234Cee234Ceed11234Ce图1.a分支语句图1.b循环语句图1.c子程序调用语句现有多路径分析方法在程序运行时，会记录程序运行过程中所有不能静态确定分支方向的条件集合CE。例如图1.a中，假设条件e依赖于外部输入，表示为DIputen，且DIputen。当程序运行至节点1进行分支选择时，运行条件会变为Ce或Ce，且会在节点1处产生新的进程进行多路径分析。假设检测点在节点2或3时，以上分析过程是没有冗余的，因为条件e或e保证了检测点的运行条件。但若检测点在节点4处，条件e和e的必要性并不明显，因为它们并未保证此时程序的运行条件。因此，需要对节点2、3、4中引用变量集和定义变量集进行更深入的分析方可确定条件e或e的必要性。易知，对于理论上最小路径条件集CE’，有'CECE。对于循环语句（图1.b）与子程序调用语句（图1.c），以上情况均会出现。因此正确选择分支条件，可以减少分支的数目和路径表达式的长度，也避免产生无用的进程进行多路径分析。定义1（路径）路径P是