一种基于动态符号执行的分布式自动测试案例生成方法

摘要

该发明属于软件测试案例自动生成技术领域中的一种基于动态符号执行的分布式自动测试案例生成方法。包括：测试设备配置，被测程序的预处理，路径约束条件的提取，测试案例的自动生成。该发明由于将被测程序与测试案例自动生成工具分离。该发明由于使被测程序在测试中可在真实平台上运行，因此所收集到的路径约束条件是遵循程序本身的语义且准确，也有助于对复杂数据结构进行分析处理，进而提高测试的可靠性和有效性，并可同时为多个被测程序进行测试及提供多种并行的多种路径选择方法；因而，本发明具有让被测程序真实平台上运行、其可行性高，可同时进行多个测试，且有效提高了测试的可靠性、准确性和测试效率，测试工具的利用率高等特点。

说明书

技术领域

本发明属于软件测试案例自动生成技术领域，该方法以路径覆盖为目标生成测试案例集， 每一个测试案例触发的被测程序执行路径都是不同的，进而实现在有限的时间内能够生成具 有高路径覆盖度的测试案例集。

背景技术

程序的一次执行过程对应着程序的一条执行路径，程序的输入参数决定程序执行的路径, 一组输入参数值称为一个测试案例。测试案例生成是软件测试过程中的重要环节，测试案例 自动生成可有效地减轻测试人员的劳动强度，降低软件开发成本，同时提高测试效率。符号 执行是一种典型的测试案例自动生成技术，主要用于测试中在给定的时间内尽可能充分地执 行程序所有可能的路径，使用满足性判定和定理证明约束求解器(以下简称SMT (SatisfiabilityModuloTheories)求解器，如YICES、STP、Z3、CVC等)自动生成对应 于这些路径的输入参数的值。传统符号执行也叫静态符号执行，是一种有效的基于程序执行 路径的静态程序分析技术。传统符号执行不真实执行程序，它使用符号变量代替程序变量的 输入值，然后基于符号变量模拟程序执行即符号执行，在执行过程中收集程序执行路径中各 个分支(if(条件表达式)then语句1else语句2)处包含符号输入的条件表达式称为符号约 束条件，程序执行结束时，符号执行就可以获得对应于每个分支点的符号约束条件，所有约 束条件的集合称为该次执行过程的路径约束条件，然后使用SMT求解器为每条执行路径所对 应的约束条件集计算满足解，生成该程序路径的一个测试案例。传统符号执行存在很多不足： 一是由于使用符号值代替真实值执行程序，当遇到二进制代码或者没有源代码的库函数时， 无法得到精确的约束条件，这样就会造成所求结果不准确，进而导致误报现象；二是在处理 大规模的或者较为复杂的程序时，由于计算复杂度过高导致无法生成具有较高路径覆盖度的 测试案例集。

动态符号执行则解决了传统方法的不足，其基本思想是使用测试案例输入参数的真实值 和符号值让程序同时进行真实执行和符号执行，真实执行反应程序的实际执行过程，符号执 行收集关于符号变量的符号约束条件，程序执行结束时，得到本次执行路径的路径约束条件。 由于被测程序真实地执行了，所以收集到的路径约束条件能够真实反映程序本身的语义，因 而在动态符号执行中不会出现如静态符号执行的误报，并且也有助于对复杂数据结构进行分 析处理。另外，由于程序的真实执行状态被记录，一旦遇到SMT求解器不可判定的路径约束 条件时便可使用程序变量的实际值替代符号值，使后续的路径搜索过程可以继续进行，因此 相比传统符号执行，动态符号执行可达到更高的覆盖率，所以被广泛的应用于程序测试与验 证中。动态符号执行使用插桩的方式来实现约束条件的提取，即在被测程序中插入一些程序 片段(函数)，这些函数可以在程序执行时提取路径约束条件并记录程序状态。目前动态符号 执行的实现方式是测试案例自动生成工具与被测程序运行在同一机器中，要求两者使用同样 的操作系统运行平台，当被测程序和工具的平台不一致时，就需要对被测程序的平台进行仿 真。目前大多只支持X86平台，然而被测程序的平台多种多样，例如仅硬件关联度较高的嵌 入式平台就有很多种，进行仿真的工作量很大，不易实现，适用性有限。同时，它使用串行 的方式，即被测程序运行一次，将收集到的路径约束条件信息传给动态符号执行工具，工具 为其生成测试案例再调用被测程序执行，如此反复，直到达到终止条件。这样，测试案例自 动生成工具中的SMT求解器进行可满足解计算时被测程序要等待SMT求解器计算结果，程序 运行时SMT求解器也要等待被测程序的执行结果，二者不可同时进行。另外，目前各工具支 持的SMT求解器很有限，且SMT求解器与测试案例自动生成工具需紧耦合，不同的SMT求解 器擅长的约束条件求解类型不同，不同类型的约束条件的最优求解器也不同，紧耦合的方式 不利于进行SMT求解器扩展。

发明内容

本发明的目的是针对背景技术存在的缺陷，研究开发一种基于动态符号执行的分布式自 动测试案例生成方法，该方法将被测程序和测试案例自动生成工具进行平台分离，使被测程 序在真实环境中执行，支持平台多样的程序测试，同时提供不同的测试覆盖标准，以提高测 试效率及满足不同的测试需求。从而达到可同时进行多个测试，并有效提高测试的可靠性和 有效性、测试工具的利用率及测试效率等目的。

本发明的解决方案是：首先将被测程序进行插桩并交叉编译为被测程序对应平台的可执 行程序，在被测程序运行的过程中通过网络标准化接口将路径约束条件传输到测试案例自动 生成工具，测试案例自动生成工具基于路径约束条件生成对应路径的测试案例，再通过网络 标准化接口将测试案例传递给被测程序继续执行，将被测程序与测试案例自动生成工具分离， 使被测程序在测试中可在真实平台上运行，从而克服了被测程序和测试案例自动生成工具的 运行平台必须一致的弊病；另外，本发明中测试案例自动生成工具采用服务器集群或云服务 平台，采用并行处技术确定多条路径约束条件的满足解，以提高测试案例自动生成的效率； 同时，提供多种遍历方法以满足不同的测试需求，除了常用的随机遍历、深度优先搜索遍历 外，还提供多种高效遍历策略，主要包括：1.并行深度优先搜索遍历，将路径决定参数的所 有取值可能分为多个范围，这些范围完全并行进行深度优先搜索遍历，既保证了执行程序的 所有路径，又可以在有限的时间内较快地获得高分支覆盖并缩短测试时间；2.基于程序CFG (Controlflowgraph，控制流图)的并行遍历，并行地以最快的方式覆盖控制流图中的每 个分支，实现程序的分支全覆盖；3.并行的随机搜索与深度优先搜索相结合的遍历，以综合 两者的优点(即随机测试的分散性和深度优先搜索的彻底性)；4.根据CFG将其中相似度较高 的路径丢弃的深度优先遍历，用以在测试大规模程序无法实现完全路径覆盖时，根据CFG丢 弃一些相似度较高的路径，在保证分支全覆盖的前提下进行非完全路径覆盖。因此，本发明 方法包括：

步骤1.测试设备配置：采用带操作系统的微机(个人电脑)、小型机作为预处理机，带 有CPU、内存和数据通信接口及操作系统的嵌入式设备作为被测程序运行装置，采用带操作 系统的服务器作为测试案例自动生成装置；预处理机与被测程序运行装置及服务器之间、被 测程序运行装置与服务器之间均分别通过通信接口连接，待用；

步骤2.被测程序的预处理：当预处理机收到被测程序后，首先采用动态符号执行技术对 被测程序中确定路径的参数变量进行符号化标识，再对源码或格式化的中间代码进行插桩处 理并在程序的每个语句前插入符号执行函数的同时提取程序的分支信息、控制流图信息，然 后将插桩处理后的被测程序交叉编译成(被测程序运行装置)嵌入式操作系统的可执行文件， 最后将可执行文件发送给被测程序运行装置、将程序的分支信息和控制流图信息发送给测试 案例自动生成装置(服务器)；

步骤3.路径约束条件的提取：被测程序运行装置在收到步骤2发送来的可执行文件后， 执行可执行文件并提取路径约束条件；

3-1.首先提取被测程序运行设备的操作系统平台基本数据类型的长度参数和包括本次测 试的被测程序名、测试类型，最大运行次数、路径选择方法在内的测试参数，发送给测试案 例生成装置(服务器)以执行步骤4、并转步骤3-2；

3-2.运行从步骤2所得可执行文件，首次运行的测试案例由步骤2插入到可执行文件中 的符号执行函数的处理符号输入语句函数(HandleSymbolic)自动随机生成，然后转3-3；

3-3.在可执行文件运行过程中利用步骤2插入到程序中的符号执行函数收集执行路径的 路径约束条件，并将所得路径约束条件发送给测试案例生成装置(服务器)以执行步骤4、 并转步骤3-4；

3-4.接收步骤4测试案例自动生成装置(服务器)发来的新的测试案例，然后转3-3重 新运行可执行文件，直至收到步骤4发出的终止信号、退出程序运行；

步骤4.测试案例的自动生成：测试案例自动生成装置(服务器)首先对由步骤2预处理 机发来的程序分支信息和控制流图进行缓存，再对被测程序运行装置中步骤3-1发送来的被 测程序运行装置的操作系统平台基本数据类型的长度参数和包括本次测试的测试参数进行测 试案例自动生成参数的配置，然后对被测程序运行装置中步骤3-3发送来的路径约束条件进 行缓存，再对路径约束条件进行格式化处理成SMT标准格式，然后并行调用SMT求解器以生 成测试案例并发送给被测程序运行装置执行步骤3-4，再接收步骤3-3发送来的新的路径约 束条件，如此循环、直到达到给定的最大运行次数且约束条件格式化处理及并行处理状态为 结束时，则发送终止信号给步骤3-4以退出程序运行。

在步骤1中所述带操作系统的预处理机，其操作系统包括Windows或Linux、MacOS； 所述被测程序运行装置，其操作系统包括Linux或uClinux、WinCE嵌入式操作系统；而所述 测试案例自动生成装置，其操作系统包括Windows、Linux。在步骤2中所述插入符号执行函 数，插入的符号执行函数为处理符号输入语句的函数(HandleSymbolic)，处理赋值语句函 数(Assignment)，处理条件语句函数(CellectConstraint)和含调用函数(Call)、返回函数 (Return)、处理返回值函数(HandleReturn)在内的处理函数调用语句函数。在步骤3-1中 所述最大运行次数由按要求设定的分支覆盖度确定。

本发明由于将被测程序与测试案例自动生成工具分离，实现了被测程序运行平台与测试 运行平台的无关性，使被测程序在测试中可在真实平台上运行，同时由于真实运行，所以收 集到的路径约束条件是遵循程序本身的语义且准确，因而在本发明方法中不会出现如静态方 法的误报，并且也有助于对复杂数据结构(如数组、指针等)进行分析处理，进而提高测试 的可靠性和有效性。本发明可以同时并行为多个被测程序进行测试，同时提供多种并行的多 种路径选择方法，提高测试工具的利用率。因而，本发明具有让被测程序真实平台上运行、 其可行性高，可同时进行多个测试，而且有效提高了测试的可靠性、准确性和测试效率，测 试工具的利用率高等特点。

具体实施方式

本实施方式以如下被测程序test.c为例：

test.c代码包括两个变量a和b，且它们都是影响程序执行过程的变量即都是确定路径的参 数，程序中有两个分支处if(a＞1)和if(a+2*b＝＝4)，有3条程序执行路径，对应的路 径约束条件及测试案例如表1所示：

表1：

步骤1为测试设备配置：预处理机采用个人电脑，操作系统为 ubuntu-12.04-desktop-amd64；被测程序运行装置使用带有网络通信接口的pandaboard开发 板，操作系统为ubuntu-12.04-preinstalled-destop-arnhf+omap4；测试案例自动生成装置 采用DellInc.PowerEdgeT620服务器，操作系统为ubuntu-12.04.5-alternate-amd64。 预处理机通过网络向被测程序运行装置传输可执行文件，预处理机通过网络向测试案例自动 生成装置传输程序的分支信息和控制流图信息，被测程序运行装置和测试案例自动生成装置 之间通过网络交互数据。

步骤2为对被测程序的预处理流程，具体描述如下：

步骤2-1：根据动态符号执行技术对待测源程序进行符号标识，即：

转步骤2-2；

步骤2-2：使用代码格式工具CIL(CommonIntermediateLanguage)对符号化标识后的 被测程序进行格式化，将其转换为格式规范的中间程序，即：

转步骤2-3；

步骤2-3：对格式化的中间程序进行插桩，即在程序的每个语句前插入相应的符号执行 函数，同时提取程序的分支信息、控制流图信息，即：

分支信息为：

12

26

45

控制流图信息为：

126

23printf

345

47printf

57printf

67printf

78

8

转步骤2-4；

步骤2-4：使用交叉编译工具arm-linux-gnueabihf-gcc将插桩后的程序交叉编译为被 测程序运行装置所运行操作系统平台的可执行文件test，然后将可执行文件test通过网络 传输至被测程序运行装置中的步骤3-1，将程序的分支信息、控制流图信息通过网络传输至 测试案例自动生成装置中的步骤4-1，转至步骤3；

步骤3为提取路径约束条件的流程，具体描述如下：

步骤3-1：获取测试参数，本例中测试参数的值为：被测程序名为test，测试类型为常 规测试，最大运行次数为5、路径选择方法为深度优先搜索，获取被测程序运行装置的操作 系统中各基本数据类型的长度，本次例中各基本数据类型的长度为：字符型char为1字节， 短整型short为2字节，整形int为4字节，长整形long为8字节，长长整形longlongint 为8字节，将各基本数据类型的长度参数和本次测试的测试参数通过网络发送给测试案例自 动生成装置，转至步骤3-2；

步骤3-2：运行可执行文件，被测程序的预处理流程插入到程序中的输入处理函数 HandleSymbolic()为进行符号化标识的变量a和b生成随机输入(本次实施案例生成为： a＝2,b＝1)，使用此输入作为测试案例转至步骤3-3；

步骤3-3：根据测试案例执行test可执行文件(如首次执行的测试案例为： a＝2,b＝1)，执行结束时，会生成本次执行的路径约束条件描述信息(a＞1∧a+2*b＝＝4)， 将执行路径的路径约束条件通过网络发送给测试案例自动生成装置，并转至步骤3-4；

步骤3-4：等待测试案例自动生成装置返回的信息(信息为新的测试案例或终止信号)， 判断收到的信息是否是终止信号，如果是，则终止程序，否则，则收到的是新的测试案例 (a＝2,b＝2)，转至步骤3-3.1；

步骤3-3.1：根据步骤3-4中收到的测试案例，本次实施案例中输入为a＝2,b＝2，调用 可执行文件test执行，执行结束时，会生成本次执行的路径约束条件描述信息 (a＞1∧a+2*b！＝4)，将路径约束条件通过网络发送给测试案例自动生成装置，转至步骤3-4.1；

步骤3-4.1：等待测试案例自动生成装置返回的信息(信息为新的测试案例或终止信号)， 判断收到的信息是否是终止信号，本例中收到的是新的测试案例(a＝2,b＝1)，转至步骤 3-3.2；

步骤3-3.2：根据步骤3-4.1中收到的测试案例，本次实施案例中输入为a＝1,b＝1，调 用可执行文件test执行，执行结束时，会生成本次执行的路径约束条件描述信息(a≤1)， 将路径约束条件通过网络发送给测试案例自动生成装置，转至步骤3-4.2。

步骤3-4.2：等待测试案例自动生成装置返回的信息，本例中收到的是终止信号，则终 止程序。

步骤4为测试案例的自动生成流程，具体描述如下：

步骤4-1：接收预处理机中步骤2-4传来的分支信息、控制流图信息，接收被测程序运 行装置中步骤3-1传来的参数，包括被测程序运行装置的操作系统中各基本数据类型的长度 和本次测试的测试参数，包括本次被测程序名为test，测试类型为常规测试，最大运行次数 为5、路径选择方法为深度优先搜索，根据测试参数，设置本次测试的被测程序名为test， 测试类型为常规测试，最大运行次数为5、路径选择方法为深度优先搜索，然后转步骤4-2；

步骤4-2：接收被测程序运行装置发来的路径约束条件组信息，判断路径约束条件是否 存在，如果存在则丢弃，否则保存路径约束条件的内容和各路径约束条件的关系，根据路径 选择方法选择出可以进行并行求解的新路径，本例中获得路径1的路径约束条件后可以生成 路径2和3的路径约束条件，2和3对应的路径约束条件分别为(a＞1∧a+2*b≠4)和 (a≤1)，将每组路径约束条件转化为SMT标准格式，根据当前SMT求解集群中的负载状态， 选择负载最小的求解服务器对通用格式的约束条件组求解以生成测试案例，本例中求解的路 径2和3对应的测试案例分别为(a＝2,b＝2)和(a＝1,b＝1)，存储测试案例到测试案例缓 存；同时监听约束条件格式化处理及并行处理状态，当无待处理路径约束条件组时返回处理 结束信号并将约束条件格式化处理及并行处理状态设置为结束，转步骤4-3；

步骤4-3：判断测试案例缓存是否为空，若不为空，则从测试案例缓存中取出一个生成 的新测试案例通过网络发送给被测程序运行装置中的步骤3-3，本例中包括传给3-3.1和 3-3.2的两个测试案例，若为空则转步骤4-4；

步骤4-4：判定生成的测试案例数量是否达到最大运行次数，如果未达到最大次数且约束 条件格式化处理及并行处理状态为真则转步骤4-2；如果达到最大运行次数则设置终止信号 为真，并向被测程序运行装置中的步骤3-4.2发送、以结束本次测试。