首页> 中国专利> 一种基于功能模型的二进制代码漏洞发现方法

一种基于功能模型的二进制代码漏洞发现方法

摘要

本发明涉及计算机软件逆向分析领域。一种基于功能模型的二进制代码漏洞发现方法,首先基于静态逆向分析系统建立代码功能模型,并基于所述代码功能模型构造初始测试用例集;其次,通过动态测试与回放分析系统依据覆盖率控制和选路策略在动态测试平台上加载测试用例集,并采用动态路径约束优化和约束求解、基于代的路径遍历算法进行测试用例集的调整,以及根据回放分析进行异常的精细分析及漏洞定位;第三,静态逆向分析系统和动态测试与回放分析系统均将各自分析得到的程序属性存入功能模型中,并以功能模型中的程序属性来指导各自的分析测试工作。能有效减少测试用例生成的盲目性,提高测试用例集的有效性,进而提高漏洞挖掘的自动化程度和效率。

著录项

法律信息

  • 法律状态公告日

    法律状态信息

    法律状态

  • 2016-05-18

    未缴年费专利权终止 IPC(主分类):G06F11/36 授权公告日:20130313 终止日期:20150329 申请日:20100329

    专利权的终止

  • 2013-03-13

    授权

    授权

  • 2010-10-13

    实质审查的生效 IPC(主分类):G06F11/36 申请日:20100329

    实质审查的生效

  • 2010-08-25

    公开

    公开

说明书

一、技术领域:本发明属于计算机软件逆向分析领域,具体地说,本发明涉及一种新的计算机软件漏洞发现技术,即一种可执行软件漏洞发现方法。

二、背景技术:二进制代码级的软件漏洞挖掘技术本质上是一种特殊类型的基于逆向分析的软件测试技术,其研究涉及各类漏洞的形成机理、软件测试理论、操作系统运行机制、静态的反汇编分析技术和动态调试跟踪技术、处理器仿真动态跟踪技术等。目前的挖掘技术从逆向分析的软件测试角度而言,可分为三类:白箱分析、黑箱分析和灰箱分析。

白箱分析包括分析和理解源代码。对于在源代码一级的软件漏洞挖掘,主要分析不安全函数的调用,给出可能导致漏洞的程序模式或匹配规则,设计一些静态分析工具,通过扫描源代码来发现漏洞。白箱分析的优点是高效快速,整个过程可以自动完成,能较全面地覆盖系统代码。而其存在的问题是通过分析会产生大量的误报,分析复杂性高,结果可用性差。2000年,美国加利福尼亚大学的David Wagner发表的“A First Step Towards Automated Detection ofBuffer Overrun Vulnerabilities”初步给出了基于源代码分析的溢出漏洞发现规则。Cigital的SourceScope、开放源码的ITS4、FlowFinder、Estima发布的RATS是几款比较典型的静态扫描分析工具,可以用以发现C或C++程序中的缓冲区溢出漏洞,其中RATS还支持Per1、PHP、Python等编程语言。

黑箱分析是指直接利用各种输入对程序进行探测,并不借助于任何源代码。黑箱分析作为软件测试的手段已经发展了很多年,理论比较成熟。通过输入非常规的命令行参数、交互时的输入、环境变量等数据来触发潜在的安全漏洞。相对于白箱分析,黑箱分析容易实施,并能够较准确和真实地确定缓冲区溢出漏洞的存在。黑箱分析的主要缺点是不能确定是否覆盖了目标程序的所有代码,而且无法处理由一组输入序列引起的安全漏洞。Fuzzing就是一种基于黑箱分析的漏洞自动检测技术。它向被测试的应用程序提供半有效性的输入,即可以被应用程序所接受并且具有一定破坏性的随机输入。它检查应用程序是否能正确处理可能的错误输入,通过监控应用程序的执行情况发现程序中潜在的漏洞。Fuzzing技术可以用于检测多种安全漏洞,包括有:缓冲区溢出漏洞、整型溢出漏洞、格式化串漏洞、竞争条件漏洞、SQL注入、跨站点脚本、远程命令执行、文件系统攻击、信息泄露等。

灰箱分析结合了白箱分析和黑箱分析技术,灰箱分析一般需要某些工具的协同工作。比如,灰箱分析在调试程序中运行目标程序,并给目标程序提供专门的输入数据集,通过这种方法在程序运行的同时检测可能的错误和漏洞。例如,Rational的Purify就是一个强大的工具,可以在软件运行时动态检查软件,提供运行时详细的内存使用和资源消耗的信息,为缓冲区溢出漏洞的发现提供依据。与灰箱分析相关的各类工具有:反汇编工具如DataRescue公司的IDAPRO、动态跟踪工具如Compuware公司的Softice、代码覆盖工具如Maryland大学的dyninst API工具等。

此外,还有基于形式化机器证明、计算机辅助推理和补丁比对等方法的漏洞发现技术。传统的漏洞发现方法有以下缺点:

(1)漏洞测试效率不高。在漏洞测试中,测试数据是随机产生的,或者有固定的模式。测试数据的产生和程序如何处理这些数据无关,另外一旦测试数据产生就是最终的测试数据,测试效率不高。

(2)漏洞测试的效果不好评估。现在常用代码覆盖率来评估漏洞测试的效果存在很多不足,因为代码覆盖率和漏洞测试效率并不存在直接联系,代码覆盖率高并不表示发现的漏洞多。

(3)异常不好排查。现有的漏洞发现方法不能自动分析异常的原因,且不能自动记录指令的执行过程。

三、发明内容:

本发明针对现有技术不足,提出一种基于功能模型进行漏洞发现的全新思路,能有效减少测试用例生成的盲目性,提高测试用例集的有效性,进而提高漏洞挖掘的自动化程度和效率,为漏洞发现的自动化和智能性、安全性测试的完备性等提供有力保障。

本发明所采用的技术方案:

一种基于功能模型的二进制代码漏洞发现方法,包括静态逆向分析系统、动态测试与回放分析系统和功能模型库,首先基于静态逆向分析系统建立起具有形式化验证和推理功能的代码功能模型,并基于所述代码功能模型构造初始测试用例集,即建立功能模型库;其次,通过所述动态测试与回放分析系统,依据覆盖率控制和选路策略在动态测试平台上加载测试用例集,对测试用例集进行动态测试,并采用动态路径约束优化和约束求解、基于代的路径遍历算法进行测试用例集的调整,以及根据回放分析进行异常的精细分析及漏洞定位;第三,静态逆向分析系统和动态测试与回放分析系统均将各自分析得到的程序属性存入功能模型中,并以功能模型中的程序属性来指导各自的分析测试工作。

所述的基于功能模型的二进制代码漏洞发现方法,通过所述的静态逆向分析系统,实现二进制代码的反汇编简化抽象表示(SAIR)、程序代码控制流分析、运行时刻环境抽取、变量取值范围分析、指针别名分析、数据结构分析还原、数据类型传播分析、脆弱点分析、污点传播分析以及路径约束生成与优化,逆向分析得到各类程序属性,并对各类程序属性进行描述分类存入功能模型中。

所述的基于功能模型的二进制代码漏洞发现方法,二进制代码的反汇编简化抽象表示(SAIR)的流程包括下述步骤:①对二进制代码文件通过反汇编器进行反汇编得到汇编程序,将可执行程序中机器指令序列转化成汇编指令序列;②提取反汇编代码,包括代码和数据、子程序信息、调用集合;③根据汇编指令的特点,对不同处理器指令系统进行分析,结合设计的描述指令相关信息属性的语法和语义实现二进制代码的反汇编简化抽象表示。

所述的基于功能模型的二进制代码漏洞发现方法,设计一种描述指令相关信息属性的语法,通过对指令语义的描述,建立从汇编代码到中间语言代码的映射,分析二进制代码的各类属性,包括程序控制流、变量的取值、数据结构还原、数据的依赖关系的需要,实现二进制代码简化汇编语言中间表示,SAIR使用以下语法分类:

①a∈Aexp,算术表达式;②b∈Bexp,布尔表达式;③I∈Ins,指令集;

假定程序的变量集合可数明确,不会出现新的立即数、标号、操作符,则SAIR对应的单词符号有以下几种:

①n∈Num,数值;②l∈Lab,标号;③Ri∈R,寄存器;④M[n]∈M,n∈Z,内存单元,M[n]∈M可简写成*(n);直接寻址的内存单元:*(n),n∈Z;间接寻址的内存单元:*(n+Ri),n∈Z,Ri∈R;⑤opa∈Opa,算术操作,Opa={+,-,*,/};⑥opr∈Opr,关系表达式,Opr={>,=,<};⑦opb∈Opb,布尔表达式,

SAIR抽象语法规则描述如下:

算术表达式:Aexp:a::=n|R0|*(n+R0)|a0 opa a1

布尔表达式:Bexp:b::=true|false|jmp l|a0 opr a1|not b|b0 opb b1

程序指令:

对于call指令标号lc用于过程调用,标号lr用于过程的返回。

所述的基于功能模型的二进制代码漏洞发现方法,在SAIR和二进制代码存储空间的抽象表示基础之上,通过静态分析程序的结构及收集程序中各个变量的使用情况建立数据流方程,并对数据流方程进行求解,以得到程序的属性信息:一个数据流分析过程等价于一个完备格程序的变量、表达式的性质或者是变量的取值等程序属性可抽象表示为格中的元素,格到格自身的映射函数f:L→L称为流函数,流函数通过格到格自身的映射来模拟程序的运行。

所述的基于功能模型的二进制代码漏洞发现方法,功能模型的建立主要通过静态逆向分析系统对二进制代码代码进行属性分析,从语法、语义上理解程序的行为,直接分析程序的特征,通过将二进制代码转化成简化汇编语言中间表示,建立指令的操作语义、抽象转移函数和代码抽象存储空间,最终建立起具有形式化验证和推理功能的代码功能模型,功能模型库中组织存放了目标代码的各类程序属性:SAIR及其形式化语义、代码控制流信息、代码数据流信息、代码抽象存储空间模型、运行时刻环境抽象表示、关键函数及其调用关系、转移点及路径约束条件、变量取值及传播范围、指针别名信息、数据依赖关系。

所述的基于功能模型的二进制代码漏洞发现方法,针对每一个二进制文件,看作是在它的逻辑地址空间上运行,过程的活动记录、堆区域以及全局数据区域在一个逻辑地址空间中,根据各区域的实际特性,把逻辑空间划分为互不相关且相对独立的存储区域,分别对其建立抽象存储空间模型,实现二进制代码存储空间的抽象表示,所述抽象存储空间模型包括:一个抽象代码域,记为AD_Code,表示程序中的可执行代码所在的区域;一个抽象静态数据域,记为AD_Data,表示程序所有初始化和未初始化的全局变量的所在的区域;若干个抽象堆域,记为AD_Heap,表示使用malloc等动态分配函数产生的内存区域;抽象栈域,记为AD_Stack,表示对应过程活动记录所在的内存区域。

所述的基于功能模型的二进制代码漏洞发现方法,程序代码控制流分析包括基于SAIR设计程序控制流分析器提取二进制代码的控制流信息、设计控制流抽象分析器对程序控制流信息进行分析和抽象、针对过程间的控制流划分基本块得到程序的控制流图并以GDL的形式显示、针对过程间的控制流分析过程的相互调用关系得到过程调用图并以GDL的形式显示。

所述的基于功能模型的二进制代码漏洞发现方法,在动态测试与回放分析系统中,采用基于代的路径遍历算法进行当前路径上新路径约束和测试用例的求解,基于代的路径遍历算法中,赋予每条路径一个N值,用于标记当前路径上已经被取反的分支约束数量,从当前路径约束生成下一代路径约束集的算法如下:

输入:thePC

输出:childPC

算法:Generation(thePC)

Len:=|thePC|;

childPC:={};

while(Len>0)do

   NewPC:=thePC[0...(i-1)]and NOT(thePC[i]);

   NewPC.N:=Len-i+1;

   childPC:=childPC+NewPC;

   Len:=Len-1;

end while

所述的基于功能模型的二进制代码漏洞发现方法,基于代的路径遍历算法指导下求得新路径约束和测试用例后,采用基于最大化代码覆盖率的路径选择策略从中选取一个进行下一轮的测试,以求在最短时间内尽可能多地覆盖基本块:统计当前测试用例能覆盖的基本块数量和新增加的基本块数量,将新增加的基本块数量作为该测试数据的权值;将该测试数据加入约束生成数据队列时,以该权值进行排序,权值大的排在队列前面;在下一轮实施约束生成和约束求解时,将从该队列头部选出第一个测试数据,即权值最大的进行优先约束生成和求解,在对约束条件进行求解时,如果该组约束条件无解,则认为该路径不可达,如果解存在,则依据约束求解的结果构造出新的测试用例,加入到测试用例集中。

本发明的有益积极效果:

1、本发明基于功能模型的二进制代码漏洞发现方法,基于二进制代码功能模型来指导漏洞发现,该机制中动态和静态安全性分析技术通过功能模型有机结合在一起,可为漏洞发现的自动化和智能性、安全性测试的完备性等提供有力保障,能极大提高漏洞发现的智能性和自动化程度。基于SAIR设计控制流分析算法屏蔽了各类CPU指令系统及其寻址方式的庞杂性,忽略了与目标平台相关的细节,使基于SAIR的漏洞分析机制适用多种不同处理器平台上可执行文件的分析。另外,控制流分析算法充分考虑了过程内和过程间控制流的特性,统一进行控制流分析,既适用于过程内控制流分析也适用于过程间控制流分析。

2、本发明基于功能模型的二进制代码漏洞发现方法,采用基于代的路径遍历算法来指导当前路径上新路径约束和测试用例的求解。此算法适用于规模较大的程序的遍历,较好地解决程序状态空间爆炸的问题;并能避免广度遍历等算法前后次遍历结果的重合;此外由于是采用的启发式搜索,能尽可能快地达到最大代码覆盖率。传统的路径遍历算法有深度遍历算法和广度遍历算法等,深度遍历算法和广度遍历算法每次遍历只生成一个新的路径约束。深度遍历算法在某个路径上不可达时会中止遍历过程;广度遍历算法在前后遍历过程中会生成重合的路径约束,影响分析效率。

3、本发明基于静态分析得到的功能模型来指导测试用例集的生成,能有效减少测试用例生成的盲目性,提高测试用例集的有效性,提高漏洞挖掘的自动化程度和效率。采用基于多重标记的动态污点分析方法,结合静态逆向分析过程中的结果,分析跟踪外部输入数据在程序具体执行过程中的流向,能很好的确定外控分支转移点中的约束条件与输入数据之间的依赖关系,能更好地产生和调整测试用例集,便于更准确的提取外控分支转移点的约束条件。

4、本发明通过基于动态污点传播的输入依赖分析能很好的得出指令与输入数据之间的依赖关系;采取程序切片方法能有效的去掉无依赖关系的指令,减少生成的约束条件规模,节省了记录程序执行轨迹和分析其动态依赖关系等所需的庞大的时间和空间开销。

四、附图说明:

图1:本发明基于功能模型的二进制代码漏洞发现方法技术架构;

图2:本发明二进制代码简化汇编语言中间表示(SAIR)转化流程;

图3:二进制代码控制流分析整体框架;

图4:二进制代码抽象存储空间模型的基本构成;

图5:单一标记和多重标记示意图。

五、具体实施方式:

实施例一:参见图1,本发明基于功能模型的漏洞发现方法,主要由静态逆向分析系统、动态测试与回放分析系统和抽象功能模型库等组成。其总体技术架构如图1所示。静态逆向分析系统和动态测试与回放分析系统均将各自分析得到的程序属性存入功能模型中,并以功能模型中的程序属性来指导各自的分析测试工作。功能模型随着动静态分析过程的不断迭代逐步调整细化。通过上述过程的相互作用和不断迭代,一方面使得功能模型更加完善与具体化,另一方面也使得逆向分析和动态测试工作更具有针对性,从而大大提高分析工作的效率和漏洞发现的可能性。

静态逆向分析系统主要实现了简化汇编语言中间表示(Simple Assemblylanguage Intermediate Representations,SAIR)、控制流分析、运行时刻环境抽取、变量取值范围分析、指针别名分析、数据结构分析还原、数据类型传播分析、脆弱点分析、污点传播分析及路径约束生成与优化等功能,并负责将逆行分析所得的各类程序属性进行描述分类存入功能模型中。

功能模型库中组织存放了目标代码的各类程序属性:SAIR及其形式化语义、代码控制流信息、代码数据流信息、代码抽象存储空间模型、运行时刻环境抽象表示、关键函数及其调用关系、转移点及路径约束条件、变量取值及传播范围、指针别名信息、数据依赖关系等。

动态测试与回放分析系统实现了基于动态测试的二进制代码漏洞分析,具有测试用例集生成和调整、用例注入和动态测试、污点分析、约束条件动态分析、覆盖率控制和选路策略、异常捕获与回放分析等功能。首先基于静态逆向分析系统得到的功能模型,构造初始测试用例集;在动态测试平台上加载测试用例集进行动态测试,采用动态路径约束优化、基于代的路径遍历和回放分析等手段进行测试用例集的调整,以及进行异常的精细分析及漏洞定位。

实施例二:参见图1~图4,本实施例在实施例一的基础上,进一步提出了建立功能模型的具体技术方案。

功能模型的建立主要通过静态逆向分析系统对二进制代码代码进行属性分析,从语法、语义上理解程序的行为,直接分析程序的特征。主要通过将二进制代码简化汇编语言中间表示(SAIR)、控制流分析、二进制代码运行时刻环境抽象表示、基于单调数据流框架的值范围分析、指针别名分析、数据结构分析还原、数据类型传播分析及数据依赖关系分析、脆弱点分析、污点传播分析及路径约束生成与优化等方法得到程序的各类属性,并将逆向分析得到的各类程序属性存入功能模型中。

功能模型反映了二进制代码的各类程序属性。依据路径遍历算法及代码覆盖率控制策略产生初始测试用例集和加载调度执行策略,为动态测试与回放分析系统提供支撑。

通过将二进制代码转化成简化汇编语言中间表示,建立指令的操作语义、抽象转移函数和代码抽象存储空间,最终建立起具有形式化验证和推理功能的代码功能模型,功能模型具有程序属性自动分析和推演的功能,并且能继承动静态分析过程所得到的程序属性和可重用特征。

为了解决大型程序测试过程中的路径爆炸问题,综合运用了抽象解释代码分析、Fuzzing测试和动态仿真等技术手段,减少测试用例生成的盲目性,提高测试用例集的有效性,在代码覆盖率指导下有效控制了测试用例集的计算复杂度,并对动态测试过程中的二进制代码覆盖率和路径覆盖率进行评估。

1、二进制代码简化汇编语言中间表示的实现

根据分析二进制代码的各类属性,如程序控制流、变量的取值、数据结构还原、数据的依赖关系等的需要,并为了保证二进制代码分析的简洁性和严密性,实现了一种简化汇编语言中间表示(SAIR)。设计一种描述指令相关信息属性的语法,通过对指令语义的描述,建立从汇编代码到中间语言代码的映射,从而完成汇编语言到SAIR的转换。本发明给出的SAIR屏蔽了各类CPU指令系统及其寻址方式的庞杂性,忽略了与目标平台相关的细节,使基于SAIR的漏洞分析机制适用多种平台可执行文件的分析。

SAIR使用以下语法分类:

①a∈Aexp,算术表达式;②b∈Bexp,布尔表达式;③I∈Ins,指令集;

假定程序的变量集合是可数明确的,不会出现新的立即数、标号、操作符等。SAIR对应的单词符号有以下几种:

①n∈Num,数值;②l∈Lab,标号;③Ri∈R,寄存器;④M[n]∈M,n∈Z,内存单元,M[n]∈M可简写成*(n)。直接寻址的内存单元:*(n),n∈Z;间接寻址的内存单元:*(n+Ri),n∈Z,Ri∈R;⑤opa∈Opa,算术操作,OPa={+,-,*,/};⑥pr∈Opr,关系表达式,Opr={>,=,<};⑦opb∈Opb,布尔表达式,

SAIR抽象语法规则可描述如下:

算术表达式:Aexp:a:=n|R0|*(n+R0)|a0 opa a1

布尔表达式:Bexp:b::=true|false|jmp l|a0 opr a1|not b|b0 opb b1

程序指令:

对于call指令标号lc用于过程调用,标号lr用于过程的返回。

从集合论的观点来看,上述规则是对汇编语言语法集合的归纳定义,由此得到的集合是对构造规则封闭的最小集。

图2是二进制代码转化SAIR的流程:

①二进制文件通过反汇编器完成二进制文件的反汇编得到汇编程序,反汇编的主要作用是将可执行程序中机器指令序列转化成汇编指令序列。

②提取反汇编代码,包括代码和数据、子程序信息、调用集合等。

③根据汇编指令的特点,对不同处理器指令系统进行分析,结合设计的SAIR语法和语义实现SAIR的转化。例如数据和地址传送指令统一划分为赋值类型的指令,跳转指令根据分析可以划分为条件分支语句。算法根据汇编指令助记符对指令分类,建立汇编指令助记符与SAIR类型的映射。在转化SAIR的时候,只是汇编指令改变,指令的操作数不变。

2、控制流分析

程序控制流分为过程内的控制流(即基于基本块的控制流)和过程间的控制流(即函数调用关系)。程序控制流分析框架如图3所示,主要包括基于SAIR设计程序控制流分析器提取二进制代码的控制流信息、设计控制流抽象分析器对程序控制流信息进行分析和抽象、针对过程间的控制流划分基本块得到程序的控制流图并以GDL的形式显示出来、针对过程间的控制流分析过程的相互调用关系得到过程调用图并以GDL的形式显示出来。

定义3个函数来提取程序的控制流:

①init:I→Lab返回指令的初始标号;

②返回指令结束标号的集合;

③映射指令的执行流集合F。

下面给出对应的程序流构造算法。算法的输入为指令集合I,此算法递归求解I的流集合F和程序的结束点集合final。其中,函数head用于取I中的第一条指令,函数tail用于得到除第一条指令外I中其余指令集合。

算法步骤如下:

输入:I

输出:f:=final(I),F:=flow(I)

算法:flow(I)

while I≠NULL do

  I′:=head(I) I:=tail(I)

  if(I′指令助记符call)then

     F:=F∪{(init(I′);init(p))}

     ∪{(l1;l2)|l1∈final(p),l2∈final(I′)}

     ∪{(init(I′),l2)|l2∈final(I′)}

  else if(I′指令助记符为retn)then f:=f∪final(I′)

  else if(I′指令助记符为jmp)then F:=F∪flow(I′)

  else if(I′指令助记符为if) then It:=head(I)

  while(It指令助记符不是else)do

     I1:=I1∪It I:=tail(I) It:=head(I)

  endwhile

    flow(if I′then I1 else I)

  else flow(I′,I)

endwhile

3、二进制代码存储空间的抽象表示

每一个正在执行的程序可看作是在它的逻辑地址空间上运行。程序逻辑地址空间由以下区域组成:

①代码区:存放可执行的目标代码。

②静态数据区:存放所有初始化和未初始化的全局变量和编译器产生的其它数据。

③堆区:存放程序运行时刻分配和释放的数据。

④栈区:存放过程的活动记录。

在程序的逻辑空间中,过程的活动记录、堆区域以及全局数据区域在一个地址空间中,但是为了分析方便,根据各区域的实际特性,把逻辑空间划分为互不相关且相对独立的存储区域,分别对其建立抽象存储模型。从而,程序存储空间抽象模型不再是简单的一维地址空间,其包含了四类抽象域:抽象代码域(记为AD_Code)、抽象静态数据域(记为AD_Data)、抽象堆域(记为AD_Heap)和抽象栈域(记为AD_Stack)。每个抽象区域均能表示程序运行时的属性,变量在具体存储空间的位置抽象表示成抽象区域中的地址。如图4所示,针对一个二进制文件,其抽象存储空间模型包含了一个抽象代码域,表示程序中的可执行代码所在的区域;一个抽象静态数据域,表示程序所有初始化和未初始化的全局变量的所在的区域;根据情况会有若干个抽象堆域AD_Heap和抽象栈域AD_Stack。抽象栈域表示对应过程活动记录所在的内存区域,抽象堆域表示使用malloc等动态分配函数产生的内存区域。基于抽象存储空间模型的运算反映了程序具体环境上的运算。

4、数据流分析和变量的传播

数据流分析在SAIR和二进制代码存储空间的抽象表示基础之上通过静态分析程序的结构及收集程序中各个变量的使用情况建立数据流方程并对数据流方程进行求解以得到程序的属性信息。程序的变量、表达式的性质或者是变量的取值等程序属性可抽象表示为格中的元素。格到格自身的映射函数f:L→L称为流函数。流函数通过格到格自身的映射来模拟程序的运行。一个数据流分析过程等价于一个完备格数据流分析实例由以下构成:

①完备格L

②指令迁移函数集合

③通过函数flow返回的流集合F

④程序的极值标号集合E,E={init(I)}

⑤极值极值表示程序入口点的初始值

⑥标号l对应的指令迁移函数fl

使用数据流分析来求得二进制代码的属性就是求下面等式的最小不动点。

R·(l)=flR(l))

τE=τif>>Eelse

上式中的R表示程序的抽象运行时刻环境,Rо(l)和R·(l)分别表示标号为l指令执行前后的运行时刻环境。通过数据流分析就可以收集可执行代码数据流信息,利用任意路径方式,可对SAIR进行到达-定义分析,建立定义-使用链(Definition-Use chains,DU)和使用-定义链(Use-Definitions chains,UD)。通过DU和UD可以精确的确定变量的使用和定义情况并能很好的对变量进行跟踪和传播。根据这些信息分析各个基本变量、函数级输入输出参数、局部堆栈数据的数据依赖关系,对关键数据结构进行传播。

如果沿着某一个路径(l1,l2,...ln)没有对变量x的定义而在ln处使用了x,那么这个路径定义为变量x的clear路径。

clear表示为:

定义du和ud表示的映射为其形式化表示为:

∪{?|clear(x,init(I*),l′)}

基于SAIR的到达-定义分析(RD)来求解ud和du链。对于每个SAIR指令:

RDin(l)={(var,?)|varFV(I*)}ifl=init(I*)U{RDout(l)|(l,l)flow(I*)}otherwise

RDout(l)=(RDin(l)\killRD(Bl))U genRD(Bl)Bl∈block(I*)

基于这种表示使用数据流分析算法即可进行到达定义分析,基于RD的程序ud链的求解公式为:

du和ud之间存在如下关系:

du(x,l)={(l′|l∈ud(x,l′)}。

du链可通过ud链来求解:

实施例三:参见图1~图5,本实施例在实施例二的基础上,进一步介绍了动态测试与回放分析系统基于功能模型的测试用例生成。其内容包括:

1、基于动态污点传播的输入依赖分析

本发明采用基于多重标记的动态污点分析方法,结合静态逆向分析过程中的结果,分析跟踪外部输入数据在程序具体执行过程中的流向,明确外控分支转移点中的约束条件与输入数据之间的依赖关系。其有助于有针对性地产生和调整测试用例集,有助于提取更准确的外控分支转移点的约束条件。

单一标记将所有的污点数据作为一个整体进行统一标记,污点数据之间没有区别。基于多重标记的动态污点分析方法将原始污点数据块进一步细分,对细分后的每一个单元分别标记,关心每一个污点单元的传播和使用情况。单一标记和多重标记的标记方式如图5所示。基于多重标记的动态污点分析方法可更细粒度和更精确反映了污点数据的传播,不仅可以确定各指令和输入数据之间的依赖关系,而且可以更加精确地确定指令依赖的具体输入。

基于多重标记的污点数据传播机制中,通过给污点数据指定IsTainted和TaintedFrom两个属性来跟踪污点数据的传播,其中IsTainted表示数据是否被污染,TaintedFrom表示当前污点数据的污点源,污点数据的污点源可能有多个,每一个污点源的TaintedFrom属性初始化为其自身。

假设污点源数据为Source,当前操作数为Dest,当Source作为操作数参与Dest的计算时,Dest污点属性更新算法如下:

I.Dest.IsTainted=1

II.Dest.TaintedFrom+=∑Source.TaintedFrom)

在污点数据传播分析中,存在指令对污点数据进行修改或重新赋值,该污点数据不再具备污点属性,此时要进行污点清除操作。主要包括三类指令:

①赋值类指令:源操作数为非污点数据或常量。

②运算类指令:所有参与运算的源操作数都是非污点数据或常量。

③部分特殊的清零性指令:源操作数虽是污点数据,污点属性应被去除,如执行xor指令对寄存器的清零操作。

2、转移点约束条件的动态生成和优化技术

路径约束(Path Constraints,简称PC)是将程序输入点到目标分支的整条路径上各转移点的约束条件通过逻辑与运算得到逻辑表达式。在测试用例的动态测试过程中,可更准确更细粒度抽取当前执行路径的路径约束条件,依次取反条件分支对应的分支约束,动态生成新的路径约束和测试数据,引导程序执行到对应的条件分支。

当目标程序规模较大时,这种生成约束条件的方法得到的路径约束规模庞大,计算开销大,难以在可接受时间范围内求解。采取如下措施减小路径约束规模:

①结合动态污点传播分析中确定的指令输入依赖关系,提出了一种基于输入依赖的精简程序切片,只生成影响目标条件分支指令处的路径约束,减少计算开销;

②采用基于关键输入的路径约束化简方法对路径约束进一步化简;

③采用基于STP的路径约束求解对路径约束进行优化。

通过基于动态污点传播的输入依赖分析得出指令与输入数据之间的依赖关系,采取程序切片方法去掉无依赖关系的指令,减少生成的约束条件规模。基于后向分析的程序切片算法的基本思想是首先记录程序的执行轨迹,通过回溯该执行轨迹以获取程序的动态依赖关系,再依据得到的动态依赖关系,从程序中删除不相关的语句,进而获得动态程序切片。基于前向分析的动态程序切片算法则无需记录程序的执行轨迹,而是在执行完一条语句或语句块之后,随即计算出当前兴趣点处变量的程序切片,节省了记录程序执行轨迹和分析其动态依赖关系等所需的庞大的时间和空间开销。基于前向分析的动态程序切片算法对影响目标条件分支的指令进行抽取。

3、基于代的路径遍历算法

基于代路径遍历算法来指导当前路径上新路径约束和测试用例的求解。按代路径遍历算法具有如下优点:

①适用于规模较大的程序的遍历,较好地解决程序状态空间爆炸的问题;

②能避免广度遍历等算法前后次遍历结果的重合;

③启发式搜索,能尽可能快地达到最大代码覆盖率。

传统路径遍历算法有深度遍历算法和广度遍历算法等。深度遍历算法和广度遍历算法每次遍历只生成一个新的路径约束。深度遍历算法在某个路径上不可达时会中止遍历过程;广度遍历算法在前后遍历过程中会生成重合的路径约束,影响分析效率。

基于代的路径遍历算法中,赋予每条路径一个N值,用于标记当前路径上已经被取反的分支约束数量。从当前路径约束生成下一代路径约束集的算法如下:

输入:thePC

输出:childPC

算法:Generation(thePC)

Len:=|thePC|;

childPC:={};

while(Len>0)do

   NewPC:=thePC[0...(i-1)]and NOT(thePC[i]);

   NewPC.N:=Len-i+1;

   childPC:=childPC+NewPC;

   Len:=Len-1;

end while

4、基于最大化代码覆盖率的路径选择策略

基于代的路径遍历算法指导下求得新路径约束和测试用例后,采用基于最大化代码覆盖率的路径选择策略从中选取一个进行下一轮的测试,以求在最短时间内尽可能多地覆盖基本块。

统计当前测试用例能覆盖的基本块数量和新增加的基本块数量,将新增加的基本块数量作为该测试数据的权值。将该测试数据加入约束生成数据队列时,以该权值进行排序,权值大的排在队列前面。在下一轮实施约束生成和约束求解时,将从该队列头部选出第一个测试数据,即权值最大的进行优先约束生成和求解。具体算法如下:

输入:inputSeed

输出:inputSet

算法:Search(inputSeed)

inputSet:={InputSeed};

  while(inputSet不为空)do

    CurrentInput:=inputSet中的第一个测试用例;

    PC=AbstractGetPC(CurrentInput);   //得到当前路径的PC

    PC.N=CurrentInput.N;

    childPCSet=Generation(PC);        //生成下一代PC集

    while(childPCSet不为空)do

       NewPC:=GetFirst(childPCSet);

       NewInput:=PCSolver(NewPC);     //约束求解

       If(NewInput为空)  //如果无解

           continue;

       NewInput.N:=NewPC.N;

       NewInput.weight:=Score(NewInput);//计算权值

       inputSet:=inputSet+NewInput;

       Sort(inputSet,weight);         //按weight权值对inputSet排序

   end while

end while

在对约束条件进行求解时,如果该组约束条件无解,则认为该路径不可达。如果解存在,则依据约束求解的结果构造出新的测试用例,加入到测试用例集中。

实施例四:本实施例基于功能模型的二进制代码漏洞发现方法,包括静态逆向分析系统、动态测试与回放分析系统和功能模型库,首先基于静态逆向分析系统建立起具有形式化验证和推理功能的代码功能模型,并基于所述代码功能模型构造初始测试用例集,即建立功能模型库;其次,通过所述动态测试与回放分析系统,依据覆盖率控制和选路策略在动态测试平台上加载测试用例集,对测试用例集进行动态测试,并采用动态路径约束优化和约束求解、基于代的路径遍历算法进行测试用例集的调整,以及根据回放分析进行异常的精细分析及漏洞定位;第三,静态逆向分析系统和动态测试与回放分析系统均将各自分析得到的程序属性存入功能模型中,并以功能模型中的程序属性来指导各自的分析测试工作。通过所述的静态逆向分析系统,实现二进制代码的反汇编简化抽象表示(SAIR)、程序代码控制流分析、运行时刻环境抽取、变量取值范围分析、指针别名分析、数据结构分析还原、数据类型传播分析、脆弱点分析、污点传播分析以及路径约束生成与优化,逆向分析得到各类程序属性,并对各类程序属性进行描述分类存入功能模型中。

去获取专利,查看全文>

相似文献

  • 专利
  • 中文文献
  • 外文文献
获取专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号