wildwolf
2005-11-25 13:55
一种面向路径的测试数据自动生成工具
单锦辉
北京大学信息科学技术学院软件研究所（100871）
随着社会的不断进步和计算机科学技术的飞速发展，计算机及软件在国民经济和社会生活等方面的应用越来越广泛和深入。作为计算机的灵魂，软件在其中起着举足轻重的作用。人们在开发软件的过程中难免会引入错误。软件的失效有可能造成巨大的经济损失，甚至危及人的生命安全。例如，1996年Ariane 5运载火箭的发射失败等都是由软件故障引起的。
软件测试是保证软件质量和可靠性的重要手段。软件测试确实能够发现软件中隐藏的许多错误。例如，在英国约克大学为英国海军开发的SHOLIS项目中，尽管采用形式化方法描述和证明软件规范，并且采用程序正确性证明方法排除了软件开发前期的许多缺陷，单元测试仍然发现了整个软件开发过程15.75%的错误。
随着人们对软件测试重要性的认识越来越深刻，软件测试阶段在整个软件开发周期中所占的比重日益增大。现在有些软件开发机构将研制力量的40%以上投入到软件测试之中；对于某些性命攸关的软件，其测试费用甚至高达所有其它软件工程阶段费用总和的3到5倍。美国微软公司软件测试人员与开发人员的比例为2比1。
现有的软件测试技术通常分为静态测试和动态测试。静态测试是不执行程序代码而寻找程序代码中可能存在的错误或评估程序代码的过程。动态测试通过在抽样测试数据上运行程序来检验程序的动态行为和运行结果以发现错误。动态测试包括三部分核心内容：生成测试用例、运行程序和验证程序的运行结果。围绕核心的辅助工作有：文档编制、数据管理、操作规程及工具应用等。动态测试最重要的问题是生成测试用例的策略。它是动态测试有效、高效的关键。测试用例包括输入数据和预期结果。一般说到测试用例生成时，由于预期结果构造的困难性，都侧重或仅生成输入数据，并称之为测试数据。
目前，测试人员一般采用手工方法设计测试数据。测试数据的自动生成将有效地减轻测试人员的劳动强度，提高测试的效率和质量，节省软件开发的成本。根据估算，对于一个典型的大型软件项目，若能自动生成测试数据，则能节省整个软件开发费用的4%，相当于数百万美元。
人们一方面开展对软件测试方法的研究，另一方面，将成熟的软件测试方法进行产品化，开发出相应的软件测试工具。目前，市场上的软件测试工具价格都非常昂贵，动辄几十万元，并且主要集中在软件测试覆盖情况的统计、测试用例的执行和管理等方面。尚未见任何真正实用的测试数据自动生成工具。与次同时，市场上对测试数据的自动生成工具有很大的需求。在我们与国外开发软件测试工具的公司的联系中得知，Raytheon、GM、Cisco、HP等公司都对测试数据的自动生成工具有迫切的需求。
在软件测试中，面向路径的测试数据生成问题可以描述为：给定一个程序P和P中一条路径W，设P的输入空间为D，求 D，使得P以 为输入运行，所经过的路径为W。软件测试中的控制流测试中诸如语句覆盖、分支覆盖、条件覆盖、判定-条件覆盖、路径覆盖等问题，数据流测试中的定义覆盖、引用覆盖等问题，组装测试中的调用对覆盖、数据流测试等问题，以及面向断言的测试和回归测试中的一些问题都可以归结为该问题。
解决面向路径的测试数据生成的关键在于约束系统的建立和求解。建立约束系统的困难是分析、化简路径W上的各种语句成分和各种数据类型，建立尽可能简洁的约束系统；求解约束系统的主要困难是处理可能存在的非线性约束。Matiyasevič和E. J. Weyuker等人的研究表明：不存在通用的有效的算法，对于任意的P和W，能生成使W被经过的程序输入。但是实际应用的需要迫使人们进行研究，并提出各种方法求解该问题。
目前，国内外面向路径的测试数据生成方法可分为四类：随机法、试探法、静态法和动态法。随机法实质上是困难的。试探法主要包括遗传算法和模拟退火法两种。遗传算法本身很复杂，其理论研究目前相当有限，结果也不太深入，作为遗传算法的理论基石之一的隐性并行性的证明还存在严重缺陷。模拟退火法的收敛速度很缓慢。静态法包括符号执行法和区间算术法，它们都需要对W上的语句进行转换，故不能用于黑盒测试。符号执行方法通常要进行复杂的代数运算，且难于处理依赖于输入变量的循环条件、数组元素下标和函数调用。区间算术法需要对变量的取值区间进行对分穷举，当变量的取值区间为无穷区间时，该方法也是困难的。动态法可分为直线式程序法和Bogdan Korel、M. Gallagher等人、Neelam Gupta等人分别提出的方法等几种。
我们经过多年的研究，在前人的工作基础上，创新地提出一种拥有自主知识产权的为指定程序路径自动生成测试数据的方法。
图1是本方法总体逻辑结构图。
图1本方法总体逻辑结构图
本方法由输入接口、词法分析器、语法分析器、约束构造器、约束求解器、路径满足检查器、输出接口模块实现测试数据自动生成。其总体逻辑结构是：用户指定程序路径W，词法分析器对W进行词法分析后，语法分析器根据词法分析的结果对W进行语法分析，将W转换为约束构造程序和路径满足检查程序，约束构造程序经编译产生约束构造器，路径满足检查程序经编译产生路径满足检查器；约束构造器根据当前程序输入和各输入变量的增量执行W上的语句，不分析W上的语句之间的数据依赖关系，计算W上各谓词函数的线性算术表示，然后建立输入变量的线性约束系统；约束求解器采用线性规划、线性整数规划、线性混合整数规划和最小二乘解法相结合的方法求解线性约束系统；求解后获得新的程序输入即测试数据；最后由路径满足检查器进行检查，若该程序输入能使W被经过则结束，若该程序输入不能使W被经过则根据W上所有谓词函数是否为输入变量的线性函数以及迭代次数上限决定是否继续迭代求解；求解结果由输出接口输出。
采用本方法进行软件测试数据自动生成可以达到如下有益效果：
1. 改进了已有的测试数据自动生成方法中构造约束系统的方法，使得本方法的构造约束系统的时间效率和空间效率更高。
2. 改进了已有的测试数据自动生成方法中求解约束系统的方法，使得本方法生成测试数据的能力更强，通用性更好，对于谓词函数均为输入变量的线性函数或者谓词函数中含有输入变量的非线性函数的一些程序路径能够有效地找到解。本方法不仅能够用于白盒测试，而且能够用于黑盒测试。当W上有循环语句而且人们不关心循环体的内部执行情况时，本方法能够直接将该循环作为一个黑盒放在W上，不必将其展开。当人们不关心W上判断语句是执行“真”分支还是“假”分支时，本方法同样可以直接将该判断语句作为一个黑盒放在W上。当W上存在函数调用或可执行程序调用时，本方法可以将被调用的函数体或可执行程序视为黑盒，不必在调用处展开，从而进一步提高了效率。本方法能够直接处理goto语句。
3. 当程序路径W上各谓词函数均为输入变量的线性函数且所有输入变量均无整数限制时，迭代一次后，本方法或者能找到所需的测试数据，或者保证该程序路径不可行。
4. 可移植性好，不受程序设计语言和操作系统的限制，易于移植到各种程序设计语言和操作系统。
5. 适用范围广，能够用于单元测试、集成（组装）测试等阶段以及面向断言的测试数据自动生成和回归测试数据的自动生成。
根据软件工程的思想，我们采用面向对象的方法，使用UML进行设计，在Windows操作系统下用C++语言和java语言对本方法进行了实现，开发出为C语言和java语言程序路径自动生成测试数据的原型工具(Path-wise Test Data Generator，简称PTDG)。
图2是PTDG的组成图。
图2 PTDG的组成图
它主要由词法分析器、语法分析器、约束构造器、约束求解器、路径满足检查器、数据文件以及用户界面组成。PTDG的图形界面采用Tcl/Tk实现（见图3）。用户只需要在PTDG运行开始时从图形界面指定程序路径W、初始输入、输入变量的增量、路径上所有谓词函数是否为输入变量的线性函数以及迭代次数上限等参数，后续的步骤由PTDG自动运行，不需要用户的干预。如果用户没有指定初始输入、输入变量的增量、路径上所有谓词函数是否为输入变量的线性函数以及迭代次数上限等参数，PTDG将使用缺省的参数值。PTDG底层的约束求解工具为Lp_solve和Matlab。在PTDG中，用户输入的程序路径、初始输入和其它参数以及PTDG运行过程中产生的中间结果和最后的求解结果均保存在文件中。
图3 PTDG的图形用户界面
图4是PTDG中设置参数的对话框，用户可以指定路径上的谓词函数是否为输入变量的线性函数，修改迭代求解的次数、输入变量的个数以及整型、浮点和双精度浮点类型输入变量在缺省情况下的初值和增量。
图4 PTDG中设置参数的对话框
在以下函数中，对于一个具有十个元素的数组X，其中各元素的值是任意输入的，要求采用冒泡排序方法对X中各元素进行排序，使得各元素按不减序排列，即X[0]<=X[1]<=X[2]<=X[3]<=X[4]<=X[5]<=X[6]<=X[7]<=X[8]<=X[9]。但是在该函数中存在一个错误，即外层循环的结束条件“i <= 7”应为“i <= 8”。
void Bubble_Sort(int X[])
{
int temp, i, j;
scanf("%d%d%d%d%d%d%d%d%d%d",
&X[0]，&X[1], &X[2], &X[3], &X[4],
&X[5], &X[6], &X[7], &X[8], &X[9]);
for (i = 0; i <= 7; i++)
for (j = 0; j <= 8; j++)
if (X[j] > X[j+1]) {
temp = X[j];
X[j] = X[j+1];
X[j+1] = temp; }
}
当在以下程序路径W1=中调用该函数，
n1: int X[10];
n2: Bubble_Sort(X);
n3: @ X[0] > X[1] @
PTDG从初始输入出发，假设各输入变量的增量为<1,1,1,1,1,1,1,1,1,-1>，经过两次迭代能够找到使W1被经过的程序输入。
上述结果表明，存在程序输入，当按照这组输入执行W1时，W1是可行的，即调用函数Bubble_Sort后，会出现“X[0] > X[1]”的结果，故违反了设计要求，从而发现函数中存在错误。上述结果也表明PTDG可以直接处理函数调用。进一步的实验表明当Bubble_Sort的函数体仅为目标代码而无源代码时，PTDG仍然能够找到相同的解，而Neelam Gupta等人提出的方法则无法构造线性算术表示。因此本方法能够用于黑盒测试。
在以下程序中，谓词函数中含有输入变量的非线性函数“x * x”。
n1: float x;
n2: scanf("%f", &x);
n3: if ( x < -1 )
n4: if ( x * x > 0 )
n5: printf("Ok!");
n6: else printf("No.");
n7: else printf("No.");
对于其中的路径W2=，从初始输入x=1出发，假设输入变量x的增量为1，PTDG所得到的如下线性约束系统
n3: x + 1 < 0
n4: 3x –2 > 0
是矛盾的，仅采用基于线性规划、线性整数规划、线性混合整数规划的约束求解方法无法进行求解，PTDG采用线性规划、线性整数规划、线性混合整数规划和最小二乘解法相结合的约束求解方法却能够经过六次迭代找到使W2被经过的程序输入-1.388210。由此可见本方法强大的寻找测试数据的能力。
我们还用其它一些实际的程序路径对PTDG进行实验。实验结果表明：PTDG能够处理的程序中的语句包括顺序、条件、循环、转移等语句，其中顺序语句包括说明语句、赋值语句、输入语句、输出语句等；能够为整数类型、浮点类型、双精度浮点类型的输入变量生成测试数据；可以直接处理数组、结构、指针和函数调用。并且可以扩充为支持布尔类型、字符类型、枚举类型。另外的实验表明PTDG能够用于面向断言的测试以及回归测试等场合的测试数据自动生成。
人们通常分单元测试、组装测试、确认测试等阶段对大型软件进行测试。本方法可以直接应用在单元测试的控制流测试中诸如语句覆盖、分支覆盖、条件覆盖、判定-条件覆盖、路径覆盖等，数据流测试中的定义覆盖、引用覆盖等方面。由于本方法能够用于黑盒测试，故本方法支持更高层次的软件测试，譬如组装测试中的调用对覆盖、数据流测试。本方法也可以用于面向断言的测试以及回归测试等方面。
单锦辉
北京大学信息科学技术学院软件研究所（100871）
随着社会的不断进步和计算机科学技术的飞速发展，计算机及软件在国民经济和社会生活等方面的应用越来越广泛和深入。作为计算机的灵魂，软件在其中起着举足轻重的作用。人们在开发软件的过程中难免会引入错误。软件的失效有可能造成巨大的经济损失，甚至危及人的生命安全。例如，1996年Ariane 5运载火箭的发射失败等都是由软件故障引起的。
软件测试是保证软件质量和可靠性的重要手段。软件测试确实能够发现软件中隐藏的许多错误。例如，在英国约克大学为英国海军开发的SHOLIS项目中，尽管采用形式化方法描述和证明软件规范，并且采用程序正确性证明方法排除了软件开发前期的许多缺陷，单元测试仍然发现了整个软件开发过程15.75%的错误。
随着人们对软件测试重要性的认识越来越深刻，软件测试阶段在整个软件开发周期中所占的比重日益增大。现在有些软件开发机构将研制力量的40%以上投入到软件测试之中；对于某些性命攸关的软件，其测试费用甚至高达所有其它软件工程阶段费用总和的3到5倍。美国微软公司软件测试人员与开发人员的比例为2比1。
现有的软件测试技术通常分为静态测试和动态测试。静态测试是不执行程序代码而寻找程序代码中可能存在的错误或评估程序代码的过程。动态测试通过在抽样测试数据上运行程序来检验程序的动态行为和运行结果以发现错误。动态测试包括三部分核心内容：生成测试用例、运行程序和验证程序的运行结果。围绕核心的辅助工作有：文档编制、数据管理、操作规程及工具应用等。动态测试最重要的问题是生成测试用例的策略。它是动态测试有效、高效的关键。测试用例包括输入数据和预期结果。一般说到测试用例生成时，由于预期结果构造的困难性，都侧重或仅生成输入数据，并称之为测试数据。
目前，测试人员一般采用手工方法设计测试数据。测试数据的自动生成将有效地减轻测试人员的劳动强度，提高测试的效率和质量，节省软件开发的成本。根据估算，对于一个典型的大型软件项目，若能自动生成测试数据，则能节省整个软件开发费用的4%，相当于数百万美元。
人们一方面开展对软件测试方法的研究，另一方面，将成熟的软件测试方法进行产品化，开发出相应的软件测试工具。目前，市场上的软件测试工具价格都非常昂贵，动辄几十万元，并且主要集中在软件测试覆盖情况的统计、测试用例的执行和管理等方面。尚未见任何真正实用的测试数据自动生成工具。与次同时，市场上对测试数据的自动生成工具有很大的需求。在我们与国外开发软件测试工具的公司的联系中得知，Raytheon、GM、Cisco、HP等公司都对测试数据的自动生成工具有迫切的需求。
在软件测试中，面向路径的测试数据生成问题可以描述为：给定一个程序P和P中一条路径W，设P的输入空间为D，求 D，使得P以 为输入运行，所经过的路径为W。软件测试中的控制流测试中诸如语句覆盖、分支覆盖、条件覆盖、判定-条件覆盖、路径覆盖等问题，数据流测试中的定义覆盖、引用覆盖等问题，组装测试中的调用对覆盖、数据流测试等问题，以及面向断言的测试和回归测试中的一些问题都可以归结为该问题。
解决面向路径的测试数据生成的关键在于约束系统的建立和求解。建立约束系统的困难是分析、化简路径W上的各种语句成分和各种数据类型，建立尽可能简洁的约束系统；求解约束系统的主要困难是处理可能存在的非线性约束。Matiyasevič和E. J. Weyuker等人的研究表明：不存在通用的有效的算法，对于任意的P和W，能生成使W被经过的程序输入。但是实际应用的需要迫使人们进行研究，并提出各种方法求解该问题。
目前，国内外面向路径的测试数据生成方法可分为四类：随机法、试探法、静态法和动态法。随机法实质上是困难的。试探法主要包括遗传算法和模拟退火法两种。遗传算法本身很复杂，其理论研究目前相当有限，结果也不太深入，作为遗传算法的理论基石之一的隐性并行性的证明还存在严重缺陷。模拟退火法的收敛速度很缓慢。静态法包括符号执行法和区间算术法，它们都需要对W上的语句进行转换，故不能用于黑盒测试。符号执行方法通常要进行复杂的代数运算，且难于处理依赖于输入变量的循环条件、数组元素下标和函数调用。区间算术法需要对变量的取值区间进行对分穷举，当变量的取值区间为无穷区间时，该方法也是困难的。动态法可分为直线式程序法和Bogdan Korel、M. Gallagher等人、Neelam Gupta等人分别提出的方法等几种。
我们经过多年的研究，在前人的工作基础上，创新地提出一种拥有自主知识产权的为指定程序路径自动生成测试数据的方法。
图1是本方法总体逻辑结构图。
图1本方法总体逻辑结构图
本方法由输入接口、词法分析器、语法分析器、约束构造器、约束求解器、路径满足检查器、输出接口模块实现测试数据自动生成。其总体逻辑结构是：用户指定程序路径W，词法分析器对W进行词法分析后，语法分析器根据词法分析的结果对W进行语法分析，将W转换为约束构造程序和路径满足检查程序，约束构造程序经编译产生约束构造器，路径满足检查程序经编译产生路径满足检查器；约束构造器根据当前程序输入和各输入变量的增量执行W上的语句，不分析W上的语句之间的数据依赖关系，计算W上各谓词函数的线性算术表示，然后建立输入变量的线性约束系统；约束求解器采用线性规划、线性整数规划、线性混合整数规划和最小二乘解法相结合的方法求解线性约束系统；求解后获得新的程序输入即测试数据；最后由路径满足检查器进行检查，若该程序输入能使W被经过则结束，若该程序输入不能使W被经过则根据W上所有谓词函数是否为输入变量的线性函数以及迭代次数上限决定是否继续迭代求解；求解结果由输出接口输出。
采用本方法进行软件测试数据自动生成可以达到如下有益效果：
1. 改进了已有的测试数据自动生成方法中构造约束系统的方法，使得本方法的构造约束系统的时间效率和空间效率更高。
2. 改进了已有的测试数据自动生成方法中求解约束系统的方法，使得本方法生成测试数据的能力更强，通用性更好，对于谓词函数均为输入变量的线性函数或者谓词函数中含有输入变量的非线性函数的一些程序路径能够有效地找到解。本方法不仅能够用于白盒测试，而且能够用于黑盒测试。当W上有循环语句而且人们不关心循环体的内部执行情况时，本方法能够直接将该循环作为一个黑盒放在W上，不必将其展开。当人们不关心W上判断语句是执行“真”分支还是“假”分支时，本方法同样可以直接将该判断语句作为一个黑盒放在W上。当W上存在函数调用或可执行程序调用时，本方法可以将被调用的函数体或可执行程序视为黑盒，不必在调用处展开，从而进一步提高了效率。本方法能够直接处理goto语句。
3. 当程序路径W上各谓词函数均为输入变量的线性函数且所有输入变量均无整数限制时，迭代一次后，本方法或者能找到所需的测试数据，或者保证该程序路径不可行。
4. 可移植性好，不受程序设计语言和操作系统的限制，易于移植到各种程序设计语言和操作系统。
5. 适用范围广，能够用于单元测试、集成（组装）测试等阶段以及面向断言的测试数据自动生成和回归测试数据的自动生成。
根据软件工程的思想，我们采用面向对象的方法，使用UML进行设计，在Windows操作系统下用C++语言和java语言对本方法进行了实现，开发出为C语言和java语言程序路径自动生成测试数据的原型工具(Path-wise Test Data Generator，简称PTDG)。
图2是PTDG的组成图。
图2 PTDG的组成图
它主要由词法分析器、语法分析器、约束构造器、约束求解器、路径满足检查器、数据文件以及用户界面组成。PTDG的图形界面采用Tcl/Tk实现（见图3）。用户只需要在PTDG运行开始时从图形界面指定程序路径W、初始输入、输入变量的增量、路径上所有谓词函数是否为输入变量的线性函数以及迭代次数上限等参数，后续的步骤由PTDG自动运行，不需要用户的干预。如果用户没有指定初始输入、输入变量的增量、路径上所有谓词函数是否为输入变量的线性函数以及迭代次数上限等参数，PTDG将使用缺省的参数值。PTDG底层的约束求解工具为Lp_solve和Matlab。在PTDG中，用户输入的程序路径、初始输入和其它参数以及PTDG运行过程中产生的中间结果和最后的求解结果均保存在文件中。
图3 PTDG的图形用户界面
图4是PTDG中设置参数的对话框，用户可以指定路径上的谓词函数是否为输入变量的线性函数，修改迭代求解的次数、输入变量的个数以及整型、浮点和双精度浮点类型输入变量在缺省情况下的初值和增量。
图4 PTDG中设置参数的对话框
在以下函数中，对于一个具有十个元素的数组X，其中各元素的值是任意输入的，要求采用冒泡排序方法对X中各元素进行排序，使得各元素按不减序排列，即X[0]<=X[1]<=X[2]<=X[3]<=X[4]<=X[5]<=X[6]<=X[7]<=X[8]<=X[9]。但是在该函数中存在一个错误，即外层循环的结束条件“i <= 7”应为“i <= 8”。
void Bubble_Sort(int X[])
{
int temp, i, j;
scanf("%d%d%d%d%d%d%d%d%d%d",
&X[0]，&X[1], &X[2], &X[3], &X[4],
&X[5], &X[6], &X[7], &X[8], &X[9]);
for (i = 0; i <= 7; i++)
for (j = 0; j <= 8; j++)
if (X[j] > X[j+1]) {
temp = X[j];
X[j] = X[j+1];
X[j+1] = temp; }
}
当在以下程序路径W1=
n1: int X[10];
n2: Bubble_Sort(X);
n3: @ X[0] > X[1] @
PTDG从初始输入
上述结果表明，存在程序输入
在以下程序中，谓词函数中含有输入变量的非线性函数“x * x”。
n1: float x;
n2: scanf("%f", &x);
n3: if ( x < -1 )
n4: if ( x * x > 0 )
n5: printf("Ok!");
n6: else printf("No.");
n7: else printf("No.");
对于其中的路径W2=
n3: x + 1 < 0
n4: 3x –2 > 0
是矛盾的，仅采用基于线性规划、线性整数规划、线性混合整数规划的约束求解方法无法进行求解，PTDG采用线性规划、线性整数规划、线性混合整数规划和最小二乘解法相结合的约束求解方法却能够经过六次迭代找到使W2被经过的程序输入-1.388210。由此可见本方法强大的寻找测试数据的能力。
我们还用其它一些实际的程序路径对PTDG进行实验。实验结果表明：PTDG能够处理的程序中的语句包括顺序、条件、循环、转移等语句，其中顺序语句包括说明语句、赋值语句、输入语句、输出语句等；能够为整数类型、浮点类型、双精度浮点类型的输入变量生成测试数据；可以直接处理数组、结构、指针和函数调用。并且可以扩充为支持布尔类型、字符类型、枚举类型。另外的实验表明PTDG能够用于面向断言的测试以及回归测试等场合的测试数据自动生成。
人们通常分单元测试、组装测试、确认测试等阶段对大型软件进行测试。本方法可以直接应用在单元测试的控制流测试中诸如语句覆盖、分支覆盖、条件覆盖、判定-条件覆盖、路径覆盖等，数据流测试中的定义覆盖、引用覆盖等方面。由于本方法能够用于黑盒测试，故本方法支持更高层次的软件测试，譬如组装测试中的调用对覆盖、数据流测试。本方法也可以用于面向断言的测试以及回归测试等方面。