一种面向路径的测试数据自动生成工具

1、种面向路径的测试数据自动生成工具单锦辉北京大学信息科学技术学院软件研究所（ 100871 ）随着社会的不断进步和计算机科学技术的飞速发展，计算机及软件在 国民经济和社会生活等方面的应用越来越广泛和深入。作为计算机的灵魂， 软件在其中起着举足轻重的作用。人们在开发软件的过程中难免会引入错 误。软件的失效有可能造成巨大的经济损失，甚至危及人的生命安全。例 如， 1996年 Ariane 5 运载火箭的发射失败等都是由软件故障引起的。软件测试是保证软件质量和可靠性的重要手段。软件测试确实能够发 现软件中隐藏的许多错误。 例如，在英国约克大学为英国海军开发的 SHOLIS 项目中，尽管采用形式化方法描

2、述和证明软件规范，并且采用程序正确性 证明方法排除了软件开发前期的许多缺陷，单元测试仍然发现了整个软件 开发过程 15.75%的错误。随着人们对软件测试重要性的认识越来越深刻，软件测试阶段在整个 软件开发周期中所占的比重日益增大。现在有些软件开发机构将研制力量 的 40%以上投入到软件测试之中； 对于某些性命攸关的软件， 其测试费用甚 至高达所有其它软件工程阶段费用总和的 3 到 5 倍。美国微软公司软件测 试人员与开发人员的比例为 2 比 1。现有的软件测试技术通常分为静态测试和动态测试。静态测试是不执 行程序代码而寻找程序代码中可能存在的错误或评估程序代码的过程。动 态测试通过在抽样测试数

3、据上运行程序来检验程序的动态行为和运行结果 以发现错误。动态测试包括三部分核心内容：生成测试用例、运行程序和 验证程序的运行结果。围绕核心的辅助工作有：文档编制、数据管理、操 作规程及工具应用等。动态测试最重要的问题是生成测试用例的策略。它 是动态测试有效、高效的关键。测试用例包括输入数据和预期结果。一般 说到测试用例生成时，由于预期结果构造的困难性，都侧重或仅生成输入 数据，并称之为测试数据。目前，测试人员一般采用手工方法设计测试数据。测试数据的自动生 成将有效地减轻测试人员的劳动强度，提高测试的效率和质量，节省软件 开发的成本。根据估算，对于一个典型的大型软件项目，若能自动生成测 试数据，

4、则能节省整个软件开发费用的 4%，相当于数百万美元。人们一方面开展对软件测试方法的研究，另一方面，将成熟的软件测 试方法进行产品化，开发出相应的软件测试工具。目前，市场上的软件测 试工具价格都非常昂贵，动辄几十万元，并且主要集中在软件测试覆盖情 况的统计、测试用例的执行和管理等方面。尚未见任何真正实用的测试数 据自动生成工具。与次同时，市场上对测试数据的自动生成工具有很大的 需求。在我们与国外开发软件测试工具的公司的联系中得知，Raythe on、GM Cisco、HP等公司都对测试数据的自动生成工具有迫切的需求。在软件测试中，面向路径的测试数据生成问题可以描述为：给定一个 程序P和P中一条路

5、径 W设P的输入空间为D,求x D,使得P以x为输 入运行，所经过的路径为 W软件测试中的控制流测试中诸如语句覆盖、分 支覆盖、条件覆盖、判定-条件覆盖、路径覆盖等问题，数据流测试中的定 义覆盖、引用覆盖等问题，组装测试中的调用对覆盖、数据流测试等问题， 以及面向断言的测试和回归测试中的一些问题都可以归结为该问题。解决面向路径的测试数据生成的关键在于约束系统的建立和求解。建 立约束系统的困难是分析、化简路径 W上的各种语句成分和各种数据类型， 建立尽可能简洁的约束系统；求解约束系统的主要困难是处理可能存在的 非线性约束。Matiyasevi ?和E. J. Weyuker等人的研究表明：不存在

6、通用 的有效的算法，对于任意的P和W能生成使W被经过的程序输入。但是实 际应用的需要迫使人们进行研究，并提出各种方法求解该问题。目前，国内外面向路径的测试数据生成方法可分为四类：随机法、试 探法、静态法和动态法。随机法实质上是困难的。试探法主要包括遗传算 法和模拟退火法两种。遗传算法本身很复杂，其理论研究目前相当有限， 结果也不太深入，作为遗传算法的理论基石之一的隐性并行性的证明还存 在严重缺陷。模拟退火法的收敛速度很缓慢。静态法包括符号执行法和区 间算术法，它们都需要对 W上的语句进行转换，故不能用于黑盒测试。符 号执行方法通常要进行复杂的代数运算，且难于处理依赖于输入变量的循 环条件、数组

7、元素下标和函数调用。区间算术法需要对变量的取值区间进 行对分穷举，当变量的取值区间为无穷区间时，该方法也是困难的。动态 法可分为直线式程序法和 BogdanKorel、M. Gallagher等人、NeelamGupta 等人分别提出的方法等几种。我们经过多年的研究，在前人的工作基础上，创新地提出一种拥有自 主知识产权的为指定程序路径自动生成测试数据的方法。图1是本方法总体逻辑结构图。程序 路径W输入变量 的初值X输入变量 的增量Y其它 参数值求解 结果*人+*输入接口输出接口词法分析器I语法分析器I路径满足 检查器 TI约束构造器I约束求解器I图1本方法总体逻辑结构图本方法由输入接口、词法分

8、析器、语法分析器、约束构造器、约束求 解器、路径满足检查器、输出接口模块实现测试数据自动生成。其总体逻 辑结构是：用户指定程序路径 W词法分析器对W进行词法分析后，语法分 析器根据词法分析的结果对 W进行语法分析，将W转换为约束构造程序和 路径满足检查程序，约束构造程序经编译产生约束构造器，路径满足检查 程序经编译产生路径满足检查器；约束构造器根据当前程序输入和各输入 变量的增量执行 W上的语句，不分析 W上的语句之间的数据依赖关系，计 算W上各谓词函数的线性算术表示，然后建立输入变量的线性约束系统； 约束求解器采用线性规划、线性整数规划、线性混合整数规划和最小二乘 解法相结合的方法求解线性约

9、束系统；求解后获得新的程序输入即测试数 据；最后由路径满足检查器进行检查，若该程序输入能使 W被经过则结束， 若该程序输入不能使W被经过则根据W 上所有谓词函数是否为输入变量的 线性函数以及迭代次数上限决定是否继续迭代求解；求解结果由输出接口 输出。采用本方法进行软件测试数据自动生成可以达到如下有益效果:1.改进了已有的测试数据自动生成方法中构造约束系统的方法，使得本方 法的构造约束系统的时间效率和空间效率更高。2.改进了已有的测试数据自动生成方法中求解约束系统的方法，使得本方 法生成测试数据的能力更强，通用性更好，对于谓词函数均为输入变量 的线性函数或者谓词函数中含有输入变量的非线性函数的一

10、些程序路 径能够有效地找到解。本方法不仅能够用于白盒测试，而且能够用于黑 盒测试。当W上有循环语句而且人们不关心循环体的内部执行情况时， 本方法能够直接将该循环作为一个黑盒放在 W上，不必将其展开。当人 们不关心W上判断语句是执行“真”分支还是“假”分支时，本方法同 3样可以直接将该判断语句作为一个黑盒放在 W上。当W上存在函数调用 或可执行程序调用时，本方法可以将被调用的函数体或可执行程序视为 黑盒，不必在调用处展开，从而进一步提高了效率。本方法能够直接处理goto语句。3.当程序路径W上各谓词函数均为输入变量的线性函数且所有输入变量均 无整数限制时，迭代一次后，本方法或者能找到所需的测试数

11、据，或者 保证该程序路径不可行。4.可移植性好，不受程序设计语言和操作系统的限制，易于移植到各种程 序设计语言和操作系统。5.适用范围广，能够用于单元测试、集成(组装)测试等阶段以及面向断 言的测试数据自动生成和回归测试数据的自动生成。根据软件工程的思想，我们采用面向对象的方法，使用UML进行设计,在Windows操作系统下用C+语言和Java语言对本方法进行了实现，开发 出为C语言和Java语言程序路径自动生成测试数据的原型工具 (Path-wise Test Data Generator ，简称 PTDG)图2是PTDG勺组成图。它主要由词法分析器、语法分析器、约束构造器、约束求解器、路径

12、 满足检查器、数据文件以及用户界面组成。PTDG勺图形界面采用Tcl/Tk实 现（见图3）。用户只需要在PTDG运行开始时从图形界面指定程序路径 W初始输入、输入变量的增量、路径上所有谓词函数是否为输入变量的线性函数以及迭代次数上限等参数，后续的步骤由PTDG自动运行，不需要用户8P TDG将使用缺的干预。如果用户没有指定初始输入、输入变量的增量、路径上所有谓词 函数是否为输入变量的线性函数以及迭代次数上限等参数, 省的参数值。PTDG底层的约束求解工具为 Lp_solve和Matlab。在PTDG中, 用户输入的程序路径、初始输入和其它参数以及 P TDG运行过程中产生的中 间结果和最后的求

13、解结果均保存在文件中。miG COrCKTL 0.? 0 16 Jiily 2001Fic. Edt. FknFAifjB灼rnclude ttrclidc n曲 ite口live mi. 15okinj lines 2I he 曲criofi eJ-44Q.7G4653S7.1.lTfl3e47.33945pros LOG:IPrOLi Varjior U.b.O - IbJu ZJQ TcfTkVcfSionaj/SJ图3 PTDG的图形用户界面图4是PTDG中设置参数的对话框，用户可以指定路径上的谓词函数是否为输入变量的线性函数，修改迭代求解的次数、输入变量的个数以及整 型、浮点和双精度

14、浮点类型输入变量在缺省情况下的初值和增量。Are al constraints on path linear?L Linear閨 NonLinearIterative Limit; | H QOINumbel of InpuWahablfts： j 1Inial Value & Incremental VaueInteger: |0hFloat: |l.a|iaDouble:|l.Oli.oOk1cartel图4 PTDG中设置参数的对话框在以下函数中，对于一个具有十个元素的数组 X,其中各元素的值是任 意输入的，要求采用冒泡排序方法对X中各元素进行排序，使得各元素按不减序排列，即X0v=X1

15、v=X2v=X3v=X4v=X5v=X6v=X7v=X8v=X9。但是在该函数中存在一个错误，即外层循环的结束条件“i = 7”应为“i = 8”。void Bubble_Sort(i nt X)int temp, i, j;sea nf(%d%d%d%d%d%d%d%d%d%d,&X0，&X1, &X2, &X3, &X4, &X5, &X6, &X7, &X8, &X9);for (i = 0; i = 7; i+)for (j = 0; j Xj+1) temp 二 Xj;Xj = Xj+1;Xj+1 = tem p; 当在以下程序路径 W1=中调用该函数,n1: i nt X10;n2

16、: Bubble_Sort(X);n3: X0 X1 输入出发，假设各，经过两次迭代能够找到使输PTDG从初始W1 入 输入变量的增量为 被经过的程序 序输，当按照上 述 结 果 表 明 ， 存 在 程 这组输入执行 W1时，W1是可行的，即调用函数 Bubble_Sort后，会出现 “X0 X1 ”的结果，故违反了设计要求，从而发现函数中存在错误。 上述结果也表明P TDG可以直接处理函数调用。进一步的实验表明当Bubble_Sort的函数体仅为目标代码而无源代码时，PTDG仍然能够找到相同的解，而Neelam Gupta等人提出的方法则无法构造线性算术表示。因此 本方法能够用于黑盒测试。在

17、以下程序中，谓词函数中含有输入变量的非线性函数“ x * x ”。 n1: float x;n2: scanf(%f, &x);n3: if ( x 0 )n5:printf(Ok!);n6:else printf(No.);n7: else printf(No.);对于其中的路径 W2=，从初始输入x=1出发，假设输入变 量x的增量为1, PTD断得到的如下线性约束系统n3: x + 1 0是矛盾的，仅采用基于线性规划、线性整数规划、线性混合整数规划的约 束求解方法无法进行求解，P TDG采用线性规划、线性整数规划、线性混合 整数规划和最小二乘解法相结合的约束求解方法却能够经过六次迭代找到 使 W 2被经过的程序输入 -1.388210 。由此可见本方法强大的寻找测试数据 的能力。我们还用其它一些实际的程序路径对 P TDGS行实验。实验结果表明： PTDG能够处理的程序中的语句包括顺序、条件、循环、转移等语句，其中 顺序语句包括说明语句、赋值语句、输入语句、输出语句等；能够为整数 类型、浮点类型、双精度浮点类型的输入变量生成测试数