基于二进制程序的测试数据生成器和方法

摘要

一种基于二进制程序的测试数据生成器和方法，其主要技术是对所述引导路径和初始测试数据对应的二进制程序的状态信息，运行动态符号执行程序，根据运行结果获得相应的条件跳转地址信息；基于所获得的条件跳转地址信息，将初始测试数据对应的实际运行路径与引导路径进行匹配；生成与所述引导路径相匹配的实际运行路径对应的测试数据。本发明结合静态分析与动态分析的优点，能提高符号执行的有效性和准确性，提高生成测试数据的准确度；还能生成用于对关键代码段进行路径敏感分析的测试数据，从而能有效缓解符号执行中遇到的路径爆炸问题。

说明书

技术领域

本发明涉及通信和计算机领域，尤其涉及一种软件安全分析领域。

背景技术

目前，在软件安全研究领域中，经常会对软件进行安全分析，在安全分析过程中一个主要问题是生成具有一定覆盖度的测试数据。无论是学术界还是产业界，普遍的安全分析方法分为动态分析方法和静态分析方法两种。

动态分析的方法通过运行所要分析的目标程序，通过人为设置不同的输入参数，使目标程序运行于不同的状态，从而观察程序内部情况或运行中产生的错误情况，以便发现安全缺陷。动态分析中最常用的方法就是FuzzTesting(模糊测试，又称之为随机数黑盒暴力测试法)。动态分析的方法自动产生测试数据，测试结果准确，适用范围广，但是效率较低，对人工依赖较大，实施过程中的不确定因素较多。

静态分析的对象可以是源代码，也可以是二进制可执行程序，一般对源代码或二进制可执行程序进行结构上或语法上的解析后，将结构化表示的内容在特定规则的情况下进行匹配识别。静态分析常用于对源代码的安全审查，也用于二进制程序，但情况较少。

目前比较常用的静态分析技术是符号执行分析技术。符号执行分析是通过符号表达式来执行程序的，也就是说程序的执行用符号来模拟：使用符号值，而不是实际数据，作为输入；将程序变量的值表示为符号表达式；程序计算的输出表达为输入符号值的函数。利用符号执行分析技术进行静态分析时，首先将程序抽象化，用符号来表示；然后构造所有可能的输入，以每个可能输入值作为输入，开始执行，执行的每一步的结果以输入值、常量和其它变量的逻辑或数学表达式来表示，直到程序结束的返回语句或者预定义的分析跳出条件被满足。一些漏洞挖掘工具常常采用符号执行分析技术，如EXE(Execution generated Executions)漏洞挖掘工具和KLEE(EXE的改进版本)漏洞挖掘工具，并取得了良好的效果。符号执行分析技术的优点是：分析是路径敏感的；因为没有对路径、状态做近似，结果精确；适合做状态检查、时序检查；对并发类型的错误十分有效；缺点有：对系统的行为进行近似，可能导致这类结果不精确；对所有可能的状态进行穷举搜索，开销大；在边界处对路径、时序属性近似困难，故复合困难。

综合上述，目前主流的静态分析技术和动态分析技术基本都存在一些问题：(1)动态测试自动生成测试数据，但测试的不确定因素较多，具有一定的盲目性，(2)静态分析效率较高，分析是路径敏感的，但在理论上存在较高的漏报率和误报率，难于准确定位漏洞；静态分析大多需要在获得源代码的基础上进行分析，针对二进制程序的符号执行技术复杂；符号执行可以自动生成测试数据进行路径遍历，但执行的路径没有针对性，且存在路径爆炸难题，自动生成测试数据进行完备的路径敏感分析不太现实。可见，二进制程序路径敏感分析还迫切需要新的突破技术。

发明内容

本发明的目的是提供一种基于二进制程序的测试数据生成器和方法，通过本发明，能够提高测试数据的准确度。

本发明的目的是通过以下技术方案实现的：

本发明提供一种基于二进制程序的测试数据生成方法，其包括：

获取所述初始测试数据对应的二进制程序的状态信息，并获取引导路径；

对所述引导路径和所述初始测试数据对应的二进制程序的状态信息，运行动态符号执行程序，根据运行结果获得相应的条件跳转地址信息；

基于所获得的条件跳转地址信息，将初始测试数据对应的实际运行路径与引导路径进行匹配；

生成与所述引导路径相匹配的实际运行路径对应的测试数据。

其中，更进一步优选的，所述基于二进制程序的测试数据生成方法，还包括：

对所述引导路径和所述初始测试数据对应的二进制程序的状态信息，运行动态符号执行程序，根据运行结果获得相应的路径约束条件信息；

对不能与所述引导路径匹配的实际运行路径对应的路径约束条件信息，进行修改；

对修改后路径约束条件信息求解，将求得的解，作为新的测试数据输入，运行动态符号执行程序。

其中，更进一步优选的，所述基于二进制程序的测试数据生成方法，还包括：

获得目标代码段；以及，通过IDA插件获得二进制程序的基本块信息和函数调用信息，通过静态分析获得二进制程序的数据流和控制流信息；

根据所获得的二进制程序的数据流和控制流信息，从所述目标代码段所在的基本块开始追溯到读取所述初始测试数据函数所在的基本块，确定出从所述初始测试数据的输入点到所述目标代码段的路径；

从所确定出的路径中确定出引导路径。

其中，更进一步优选的，所述从所确定出的路径中确定出引导路径的过程，包括：

判断所确定出的路径中是否存在未处理的路径；若有，则从中选择一个作为引导路径；否则，则转入获得目标代码段的过程。

其中，更进一步优选的，所述获得目标代码段的过程，包括：

通过IDA插件获得危险函数代码段或危险操作代码段；根据所述危险函数代码段或危险操作代码段，设定目标代码段；

或者，

获取用户输入的目标代码段。

本发明还提供一种基于二进制程序的测试数据生成器，其包括：

动态符号执行模块，用于所述初始测试数据对应的二进制程序的状态信息和引导路径；对所述引导路径和所述初始测试数据对应的二进制程序的状态信息，运行动态符号执行程序，根据运行结果获得相应的条件跳转地址信息；

路径引导模块，用于基于所获得的条件跳转地址信息，将初始测试数据对应的实际运行路径与引导路径进行匹配；

测试数据生成模块，用于生成与所述引导路径相匹配的实际运行路径对应的测试数据。

其中，更进一步优选的，所述动态符号执行模块，还用于对所述引导路径和所述初始测试数据对应的二进制程序的状态信息运行动态符号执行程序，根据运行结果获得相应的路径约束条件信息；

所述基于二进制程序的测试数据生成器，还包括：路径修订模块，用于对不能与所述引导路径匹配的实际运行路径对应的路径约束条件信息，进行修改；对修改后的路径约束条件信息求解，将求得的解作为新的测试数据输出给所述动态符号执行模块。

其中，更进一步优选的，所述基于二进制程序的测试数据生成器，还包括：

用户接口模块，用于获得目标代码段；

路径确定模块，用于获得二进制程序的基本块信息和函数调用信息，通过静态分析获得二进制程序的数据流和控制流信息；根据所获得的二进制程序的数据流和控制流信息，从所述目标代码段所在的基本块开始追溯到读取所述初始测试数据函数所在的基本块，确定出从所述初始测试数据的输入点到所述目标代码段的路径；从所确定出的路径中确定出引导路径。

其中，更进一步优选的，所述路径确定模块，包括：

路径回溯单元，用于根据所获得的二进制程序的数据流和控制流信息，从所述目标代码段所在的基本块开始追溯到所述初始测试数据所在的基本块，确定出从所述初始测试数据的输入点到所述目标代码段的路径；

引导路径确定单元，用于判断所确定出的路径中是否存在未处理的路径；若有，则从中选择一个作为引导路径；否则，触发所述用户接口模块。

其中，更进一步优选的，所述基于二进制程序的测试数据生成器，还包括：

调试器，负责加载二进制程序使其处于调试运行状态，并解析初始测试数据，得到与所述初始测试数据对应的二进制程序的状态信息，并将与所述初始测试数据对应的二进制程序的状态信息提供给所述动态符号执行模块。

由上述本发明提供的技术方案可以看出，本发明由于结合了静态分析与动态分析的优点，采用了动态执行的方法获得实际执行环境中的数据，相对于静态分析技术，能够提高符号执行的有效性和准确性，从而能够提高生成测试数据的准确度。

另外，本发明关注于特定的目标代码段，能够生成能够有针对性的用于对关键代码段进行路径敏感分析的测试数据，从而能够有效缓解符号执行中遇到的路径爆炸问题。

附图说明

图1是本发明第一实施例中基于二进制程序的测试数据生成器的结构原理图。

图2是本发明第二实施例中基于二进制程序的测试数据生成方法的流程图。

图3是本发明第二实施例中确定引导路径过程的流程图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明作进一步的详细描述。

本发明第一实施例提供一种基于二进制程序的测试数据生成器，该基于二进制程序的测试数据生成器是从基于二进制程序的初始测试数据入手，结合实际执行和符号执行解决软件安全检测面临的问题。为缓解路径爆炸问题，该基于二进制程序的测试数据生成器关注存在安全危险的代码部分，根据输入的二进制程序，利用动态符号执行技术，能够在不需要源代码的条件下，自动生成能够使此基于二进制程序的初始测试数据的输入点沿着所有可能的不同路径实际执行到达目标代码段的测试数据集。其结构原理图如图1所示，包括如下模块：

调试器10、用户接口模块20、路径确定模块30、动态符号执行模块40、路径引导模块50，路径修订模块60、测试数据生成模块70。

调试器10，用于负责加载二进制程序使其处于调试运行状态，并解析初始测试数据，得到与所述初始测试数据对应的二进制程序的状态信息，并将与所述初始测试数据对应的二进制程序的状态信息提供给所述动态符号执行模块。该调试器10的具体情况如下：

调试器10，负责加载二进制程序并使其处于调试运行状态，解析PE(Portable Executable，可移植的执行体)文件(PE文件是win32平台下可执行文件遵守的数据格式)结构，获得与初始测试数据对应的二进制代码和相关信息。该调试器10，还可以提供包括断点、单步执行、远程内存和寄存器访问等功能，为动态符号执行提供运行环境，并在运行过程中为符号执行获取寄存器和内存中的数据。

用户接口模块20，用于获得目标代码段。该用户接口模块20的具体情况如下：

该用户接口模块20主要负责与用户进行交互，一方面用于获取用户自定义需测试分析的目标代码段，或从系统自动提供的具有潜在安全危险的危险函数代码段或危险操作代码段中选择需测试分析的目标代码段；另一方面，该用户接口模块20，还负责记录测试数据生成模块生成的与到达目标代码段的各个实际执行路径相对应的测试数据。

路径确定模块30，用于获得所述初始测试数据的二进制程序(即PE文件)的基本块信息和函数调用信息，通过静态分析技术获得二进制程序的数据流和控制流信息，根据获得的二进制程序的数据流、控制流信息和所述用户接口模块20输出给的需测试分析的目标代码段，从所述目标代码段所在的基本块开始追溯到所述初始测试数据所在的基本块，确定出从所述初始测试数据的输入点到所述目标代码段的路径；将所确定出的路径作为引导路径。

所述路径确定模块30，具体包括：路径回溯单元301和引导路径确定单元302。

路径回溯单元301，用于获得所述初始测试数据的二进制程序的基本块信息和函数调用信息，通过静态分析获得二进制程序的数据流和控制流信息；并根据所获得的二进制程序的数据流、控制流信息和所述用户接口模块20所获得的需测试分析的目标代码段，从所述需测试分析的目标代码段所在的基本块开始追溯到读取所述初始测试数据函数所在的基本块，确定出从所述初始测试数据的输入点到所述目标代码段的路径。具体情况如下：

路径回溯单元301，通过IDA(Interactive Disassembler，交互式反汇编程序)插件，获得读取所述初始测试数据的二进制程序的汇编代码的基本块信息和函数调用等信息，并通过静态分析获得二进制程序的数据流和控制流信息，在此基础上从目标代码段所在基本块开始，通过一步步向前追溯前驱块，最终回溯到所述初始测试数据的二进制程序输入API(ApplicationProgramming Interface，应用编程接口)函数所在基本块，获得从所述初始测试数据的二进制程序的输入点到达所述目标代码段的一条条不同路径，如果路径中的有循环，则将循环体按照循环次数的不同将路径循环扩展为子路径集；

引导路径确定单元302，用于判断所述路径回溯单元301所确定出的路径中是否存在未处理的路径；若有，则从中选择一个作为引导路径；否则，触发所述用户接口模块20获取新的目标代码段。具体情况如下：

引导路径确定单元302首先判断路径回溯单元301所确定出的路径中是否存在未处理的路径；若有，则从中选择一个作为引导路径用于引导程序的执行，标记已作为引导路径的路径，并在其余的路径中选择新的引导路径；若发现路径回溯单元301所确定出的路径都被处理过，则触发所述用户接口模块20获取新的目标代码段。

动态符号执行模块40，用于从所述路径确定模块30中获取引导路径，从所述调试器10中获取所述初始测试数据对应的二进制程序的状态信息；并对所述引导路径和所述初始测试数据对应的二进制程序的状态信息，运行动态符号执行程序，根据运行结果获得相应的条件跳转地址信息，以及，相应的路径约束条件信息；具体情况如下：

动态符号执行模块40，将静态符号执行与动态实际执行相结合，使用符号值，而不是实际数据，作为输入；将程序变量的值表示为符号表达式；程序计算的输出表达为输入符号值的函数。该模块的输出是符号变量控制的路径约束条件集合和条件跳转地址信息。这里动态符号执行模块40负责将所述引导路径、所述初始测试数据对应的二进制程序的状态信息和通过反汇编获得的指令信息结构体作为输入，输出是：实际执行路径的路径约束条件集合和条件跳转地址信息，这些输出都是符号变量的表达式。将输出的约束条件集合和条件跳转地址信息提供给路径引导模块50；

路径引导模块50，用于基于所获得的条件跳转地址信息，将初始测试数据对应的实际运行路径与引导路径进行匹配；获得与所述引导路径相匹配的实际运行路径，或者，不能与所述引导路径匹配的实际运行路径。

路径修订模块60，用于对不能与所述引导路径匹配的实际运行路径对应的路径约束条件信息，进行修改；对修改后路径约束条件信息求解，将求得的解作为新的测试数据输出给所述动态符号执行模块。

通过动态符号执行模块得到与引导路径有关的路径约束条件信息集合，得到的路径约束条件信息符合STP(Simple Theorem Prover，简单定理证明器)约束求解器语法规范的表达式输出，这样可以通过STP约束求解器，对修正后的路径约束条件信息集合求解，若有解，则将该解对应的路径约束信息集合，作为新的测试数据输入，这样不断的调整测试数据输入，以便使程序沿着引导路径最终实际执行到目标代码段；对路径约束条件信息求解无解的，则说明当前被引导的实际执行路径为实际不可达的路径，将其标识为不可行路径，结束该当前引导路径的引导，并排除该不可行的被引导的路径(即实际执行的路径)。

路径修订模块60在对路径约束条件信息进行修改时，一般遵循如下规则：

首先识别实际执行路径中的call语句；

如果与引导路径的条件跳转地址信息不符的跳转节点的前一个路径节点为call语句，则从最后一个路径约束条件信息起，向前依次求反：若之前没有对运行到的最后一个跳转节点对应的跳转条件求反过，则对它求反；如果已求反，但再次运行实际执行路径时，条件跳转地址信息与引导路径的仍不符，则继续向前对它的前一个跳转节点对应的跳转求反；

如果某一个跳转节点对应的跳转条件被取反后，则其后跳转条件作废。

如果与引导路径的条件跳转地址信息不符的跳转节点的前一个路径节点不是call语句，则仅对最后一个跳转条件求反。

测试数据生成模块70，用于生成与所述引导路径相匹配的实际运行路径对应的测试数据。

测试数据生成模块70为可行的被引导路径自动生成相应的测试数据，即生成沿被引导的路径实际执行到目标代码段的测试数据，这样可以使程序沿着可行被引导的路径执行到达目标代码段。

上述实施例中还可以包括反汇编模块，负责将调试器10获得的二进制代码反汇编成汇编指令，再将该汇编指令按其格式分解为操作类型、操作数和操作数位数，填充到指令信息结构体中，供动态符号执行模块40使用；

上述二进制代码可以是来自于Windows平台下所有PE格式的EXE文件和相关DLL文件代码，即可用于Windows平台下任意的可执行程序。

为了达到上述目的，本发明第二实施例还提供了一种基于二进制程序的测试数据生成方法，其流程图如图2所示，包括下列操作步骤：

步骤201，获取初始测试数据对应的二进制程序的状态信息；然后转入步骤203。

首先输入需要测试的二进制程序并通过利用在IDA Pro逆向工具上开发的插件获得的数据文件，并提供初始测试数据对应的二进制程序的状态信息；

随后通过反汇编处理，按反汇编程序的格式，将所述初始测试数据对应的二进制程序的状态信息的机器码，解析成操作类型、操作数和操作数位数，并填入到指令信息结构体，然后转入步骤203。

步骤202，获得目标代码段。

具体获得目标代码段的方法有如下2种：

其一是：通过IDA插件获得具有潜在安全危险的危险函数代码段或危险操作代码段；根据所述危险函数代码段或危险操作代码段，设定目标代码段；

另外一种是：获取用户输入的目标代码段。

步骤203，回溯得到从读取所述初始测试数据的二进制程序的输入点到达所述目标代码段的路径。

通过IDA插件获得二进制程序的基本块信息和函数调用信息，通过静态分析获得二进制程序的数据流和控制流信息；根据所获得的二进制程序的数据流和控制流信息，从目标代码段所在基本块开始通过一步步向前追溯前驱块，最终回溯到所述初始测试数据的二进制程序输入API(ApplicationProgramming Interface，应用编程接口)函数所在基本块，获得从所述初始测试数据的二进制程序的输入点到达所述目标代码段的一条条不同路径，如果路径中的有循环，则将循环体按照循环次数的不同将路径循环扩展为子路径集。

此处的到达用户所指定的目标代码段的所有路径，可以用路径中的汇编跳转指令的地址的顺序排列表示。此处的汇编跳转指令可以是如下中的任意一种：call、ret、je、jz、jnz、jne、jmp、jle、jng、jl、jnge、jge、jnl、jg、jnle、jo、jno、jb、jc、jnb、jnc、jbe、jna、ja、jnbe、js、jns、jpe、jp、jpo、jnp、jecxz。

步骤204，确定引导路径

根据深度优先策略，在回溯路径中获得的一条未经过路径引导处理的路径作为引导路径，并标记该条引导路径为已经用作引导的引导路径，然后执行步骤205，对含有循环的路径，按不同的循环次数将路径扩展分为不同的子引导路径，并依次进行处理；当所有的路径都经过引导处理后，转到步骤202。

该步骤204中确定引导路径的具体流程如图3所示，包括如下步骤：

步骤301，采用深度优先遍历从回溯路径中获得一条路径；

步骤302，判断该引导路径中是否存在循环，若存在循环，则执行步骤303；否则，执行步骤306；

步骤303，循环扩展路径。

步骤304，判断循环扩展子路径集是否遍历，若否，则执行步骤305；否则，执行步骤307。

步骤305，选择一条子路径作为一条引导路径，然后转入步骤304。

识别路径中的循环时，对含有循环的路径进行不同次数的循环扩展获得循环扩展子路径集，并将不同次数循环扩展之后得到的循环扩展路径集作为子引导路径集。

步骤306，选择该路径作为引导路径。

步骤307，标记当前引导路径已经被处理，然后转入步骤301。

标记已经经过引导处理过的引导路径，然后转入步骤301，即继续深度优先遍历获得一条未执行过的引导路径来引导程序运行。

步骤205，对所述引导路径和所述初始测试数据对应的二进制程序的状态信息，运行动态符号执行程序，根据运行结果获得相应的条件跳转地址信息，和相应的路径约束条件信息。

步骤206，基于所获得的条件跳转地址信息，将初始测试数据实际运行路径与引导路径进行匹配；若实际运行路径与所述引导路径相匹配，则转入步骤211；否则，执行步骤207；

步骤207，根据所述路径约束条件信息，修改不能与所述引导路径匹配的实际运行路径对应的路径约束条件信息。

步骤208，对修改后的路径约束条件求解。

步骤209，判断是否有解，若有解，则执行步骤210，即将求得的解作为PE文件的新的测试数据输入，重新加载。然后转入步骤205，运行动态符号执行程序；若无解，转入步骤211。

在步骤206至步骤210的程序运行过程中，根据动态符号执行程序的运行结果，比较程序实际运行的路径与引导路径的条件跳转地址记录是否符合，这里，可以通过比较路径所经过的汇编跳转指令的地址顺序来进行比较。如果程序实际路径的条件跳转地址记录与引导路径的条件跳转地址记录不符，则结束该过程，获得由步骤206得到的与输入有关的路径约束条件，对最后跳转方向不符的路径约束条件进行求反修订(具体执行过程与第一实施例中的相关描述类似，这里不再详细描述)，获得沿引导路径进一步运行的路径约束条件，并通过STP约束求解器，对修订后的路径约束条件求解，将求得的解对应的路径约束信息作为新的测试数据，并重新加载程序，返回步骤205。如果修订后的路径约束条件无解，则标识当前被引导的实际执行路径为不可行路径，返回步骤202进行下一条路径的引导。

步骤211，结束当前被引导的路径。

步骤212，生成与所述引导路径相匹配的实际运行路径对应的测试数据。然后转到步骤202，根据新的目标代码段进行路径引导。

上述实施例中提及到的具有潜在安全危险的危险函数代码段或危险操作代码段中，危险函数有：gets、_getws、strcpy、wcscpy、_mbscpy、lstrcpyA、lstrcpyW、strcat、wcscat、_mbscat、lstrcatA、lstrcatW、strncpy、wcsncpy、_mbscbcpy、lstrcpynA、lstrcpynW、strncat、wcsncat、_mbsnbcat、memcpy、memmove、CopyMemory、MoveMemory、printf、fprintf、sprintf、wprintf、fwprintf、swprintf、vprintf、vfprintf vsprintf、vwprintf、vfwprintf、vswprintf、scanf、fscanf、sscanf、wscanf、fwscanf、swscanf、wsprintfA、wsprintfW；危险操作有：rep movsd、rep movsb。

由上述实施例可以看出，本发明相对于目前其他相关技术，主要存在如下技术创新点：1、对二进制代码的分析，采用符号执行技术和动态实际执行相结合，保证了符号执行在二进制代码分析中的可行性和精确性。2、仅分析与输入测试数据有关的路径约束条件，简化了静态分析的复杂度。3、关注于特定的目标代码段，有选择、有重点的进行测试。4、关注于特定的目标代码段，获取所有到达路径，引导路径是完备的，最终得到的测试数据集对应到达目标代码段的全路径。5、采用路径引导结合实际执行的方法规约路径约束条件，通过约束求解器求解获得测试数据。6、为特定的具体路径寻获对应的输入数据，产生的每个测试数据与每条不同的具体引导路径是一一对应的。

由此可见，本发明由于结合了静态分析与动态分析的优点，采用了动态执行的方法获得实际执行环境中的数据，相对于静态分析技术，能够提高符号执行的有效性和准确性，从而能够提高生成测试数据的准确度。

另外，本发明关注于特定的目标代码段，能够生成能够有针对性的用于对关键代码段进行路径敏感分析的测试数据，从而能够有效缓解符号执行中遇到的路径爆炸问题。

另外，采用路径引导结合程序实际执行的方法，生成方式简约，生成的测试数据更加的准确。

另外，相对于静态符号执行技术，采用路径引导的方式，可以方便的处理二进制程序中的循环，使得符号执行的结果也更加准确有效。

另外，本发明可以对任意的目标代码段的检测进行测试数据的生成，从而使有选择、有重点的进行软件测试成为可能。

另外，本发明为特定的具体路径生成对应的输入数据，具有普遍适用性和可扩展性，结合符号执行还可以用于污点传播分析、漏洞分析，也适用于进行路径遍历。

另外，具有更普遍的适用性，本二进制程序测试数据生成器只需要分析可执行程序本身而不需要提供源代码。

另外，本测试数据生成的方法针对windows平台，但采用的测试数据生成的方法与技术具有通用性，因此可以方便的移植到Linux平台。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。