测试数据生成范文

测试数据生成范文（精选8篇）

测试数据生成 第1篇

关键词：软件测试,遗传算法,路径覆盖,测试数据生成,原型系统

0 引言

软件测试是软件开发中不可缺少的环节, 是软件工程的重要组成部分, 测试的效果直接关系到软件产品的质量。已有统计结果表明, 软件测试占整个软件开发周期总成本的50%以上, 包括:说明测试需求、准备测试数据、执行测试, 以及评价与分析测试结果等耗时、枯燥也是非常困难并容易出错的环节。在软件测试工作中, 最重要的环节就是测试数据的生成, 这也是非常耗时的一个环节, 测试数据的合理、准确与否常常关系到整个测试的成败。因此, 如果将该环节自动化, 无疑将会缩短软件的开发周期, 提高软件质量。

目前, 国际和国内的一些研究机构针对不同语言编写的程序, 开发出路径覆盖测试数据生成系统, 其中, Scott开发的系统是针对Fortran语言的, 但只考虑了有限的Fortran语句, 如if语句, 和一些简单的算术分支谓词和变量类型;Ferguson和Korel开发了一个名为TESTGEN的测试数据生成系统, 该系统支持Pasca1语言编写的程序模块的测试数据生成。这个系统具有以下限制:只支持整型数据的生成、简单的算术和布尔分支谓词, 以及Pascal语言的一个子集;此外, 一些很重要的元素却不能应用, 如过程等[1]。刘义等开发了一个C程序路径覆盖及测试数据自动生成系统, 该系统只针对分支覆盖准则;陈继锋等[2]设计了一种面向路径的测试数据自动生成工具, 但是, 使用的测试数据生成方法是基于改进后的松弛迭代法, 需要用户实现的初始操作多, 从而对非专业的软件测试人员难以使用;周晓宇等[3]设计了两两组合覆盖测试数据自动生成工具, 但该工具生成的测试数据都只是最优值的近似解;李宝林等[4]提出的面向路径的测试数据自动生成工具采用的是遗传模拟退火算法, 在路径选择和测试数据生成方法方面均有待改进。

上述系统大多未使用遗传算法或仅使用传统的遗传算法, 遗传算法的个体编码方式、适应值计算、选择方式、交叉方式, 以及变异方式等均只有一种方法, 测试数据生成的效率有待提高。鉴于此, 使用VC++6.0开发一套基于遗传算法的路径覆盖测试数据自动生成系统, 该系统不仅能够根据用户选择的测试路径, 使用遗传算法自动生成穿越目标路径的测试数据, 而且在生成测试数据的过程中, 分别提供了多种遗传算法个体编码、适应值计算、选择、交叉, 以及变异方式等, 可根据不同类型的被测程序选择不同的测试数据生成方法, 以用于C或C++语言编写的被测软件测试数据自动生成。

1 路径覆盖测试数据自动生成系统的结构

路径覆盖测试数据自动生成系统的工作原理:对于给定的被测程序, 首先生成程序的控制流程图 (CFG) ;然后根据CFG由用户选择待测目标路径P, 系统内采用赫夫曼编码方式对目标路径P编码;最后使用遗传算法自动生成穿越目标路径P的测试数据。该系统分为三个模块:被测程序分析模块、测试系统界面管理模块, 以及测试数据生成模块。系统流程如图1所示。

1.1 被测程序分析模块

被测程序分析模块功能包括:被测程序分析、控制流程图生成, 以及目标路径生成等。在对被测程序测试之前, 首先要对被测程序的输入变量及程序的结构等进行人工分析, 得到与待测路径和测试数据生成相关的信息;然后根据被测程序的结构特征, 生成程序的控制流程图;最后通过控制流程图提供的路径信息, 在被测程序所有可能的路径中选择一条或多条路径作为目标路径, 并采用赫夫曼编码将目标路径表示成二进制串。目标路径是测试数据生成的输入参数之一, 根据目标路径编码设计适应度函数, 能够有效提高测试数据生成的效率。

1.2 系统界面管理模块

系统界面管理模块通过一个交互界面负责与用户交互, 包括接收用户的输入及输出相应的信息, 主要功能有被测程序插装、测试系统输入输出处理、系统外部变量处理, 以及客户测试参数设置等。

在执行被测程序过程中, 为了反映测试数据在程序执行中穿越的路径, 需要在被测程序中插入一些变量, 用变量的不同值代表执行分支语句的不同走向, 并用数组存放变量的取值。由于该系统采用赫夫曼编码方式表示路径, 被测程序插装时只需考虑分支语句, 大大简化了插装的工作量。

测试数据生成系统的运行方式主要由测试参数决定的, 不仅涉及到问题的描述及测试路径的选择, 而且涉及到模块之间的通信。例如, 除了遗传算法的选择、交叉和变异算子, 以及染色体编码方式和适应度函数等策略外, 被测程序分析模块得到的输入变量和目标路径也需设置后, 才能使系统按照用户的需求正常运行。生成的程序控制流程图将在系统交互界面的图形窗口中以图像的方式显示, 以指导测试路径的选择, 生成的测试数据则以表格的形式给出, 包含每条目标路径对应的测试数据、生成该数据所需的运行代数, 以及运行时间等信息。

1.3 测试数据生成模块

测试数据生成模块是系统的核心, 主要功能是根据上述用户设定的策略和参数, 调用系统相应的函数, 生成被测程序的测试数据, 以及与界面管理模块交互。

在使用遗传算法生成被测程序的测试数据之前, 需要首先接收系统界面管理模块传递的策略和参数, 包括选择、交叉和变异算子, 交叉和变异概率, 种群规模, 进化终止代数, 染色体编码方式, 适应度函数, 被测程序的输入变量, 测试路径, 实验次数, 以及种群的初始化方法等;然后调用算法相应的函数, 在后台完成测试数据生成的功能, 并将生成的测试数据传递给系统界面管理模块, 在系统界面中显示出来。

2 遗传算法的路径覆盖测试数据自动生成方法

使用遗传算法生成被测程序的测试数据时, 首先随机生成算法的初始种群, 然后重复做以下操作:解码进化个体、运行被测程序, 以及检查是否有个体穿越目标路径。若有, 则记录该个体, 删除找到的目标路径。如果没有满足终止条件, 计算个体适应值并执行选择、交叉和变异操作, 以生成新的种群, 直到覆盖全部目标路径的测试数据找到, 或者达到最大进化代数为止。此时, 终止算法并解码最优个体, 以得到期望的测试数据。

2.1 目标路径描述

目标路径采用赫夫曼编码方式表示, 赫夫曼编码是以分支节点的执行情况表示路径, 若分支语句的真分支采用1表示, 假分支采用0表示, 那么, 该程序的一条路径就可以用二叉树[5]的叶结点的赫夫曼编码表示, 这样, 路径编码能保证任何一个目标路径的编码都不是其他编码的前缀。根据目标路径编码, 设计3种目前国内外研究比较成熟的适应度函数, 有效改进了测试数据的生成效率。

2.2 适应度函数

适应度函数是遗传算法与被测程序的接口, 对遗传算法的收敛速度和生成的测试数据影响很大, 因此, 将测试数据生成问题转化为函数优化问题的关键是适应度函数。依据前期的理论和实践, 在测试数据自动生成系统中, 使用的适应度函数有以下3种:层接近度、分支距离, 以及层接近度和分支距离的综合。

2.3 个体编码方式

个体的编码方式直接影响进化种群的遗传操作以及测试数据生成的效率。根据软件测试的实际需求, 系统提供了遗传算法常用的3种编码方式:二进制编码、格雷码编码, 以及实数编码, 供用户在生成测试数据时根据需求选择。

2.4 遗传算子

在测试数据生成系统中, 遗传算法在控制参数下的运行过程如图2所示。首先系统接收用户设置的控制参数;然后调用遗传算法相应的函数对种群进行选择、交叉和变异操作, 从而产生新种群;最后解码新种群中的最优个体, 获得期望的测试数据。如此循环, 直到找到全部期望的测试数据为止。在测试数据生成过程中, 选择、交叉和变异操作均通过控制参数的设置进行调用。

选择算子根据个体的适应值, 按照一定的规则, 从当前种群中选择优良个体遗传到下一代种群[6]。系统采用了3种常用的选择方法, 分别是:轮盘赌、随机联赛和随机竞争。

交叉算子体现了信息的交换思想, 将当前种群内的各个体随机搭配成对, 对每一对个体, 以某概率 (称为交叉概率Pc) 交换它们之间的部分染色体。交叉概率可在系统的交互界面中设定, 其大小直接影响交叉算子的性能。系统提供了3种交叉方法可供用户选择:单点交叉、多点交叉和均匀交叉。

变异算子对个体编码串的某些基因位上的基因值作变动, 变异概率Pm的大小可在系统的交互界面中设定, Pm的大小也直接影响算法的性能[6]。不同的编码方式的变异算子也不尽相同。根据上述3种个体编码方式, 系统提供了4种变异算子:基本位、实值、均匀和非均匀变异。

基于遗传算法的测试数据自动生成步骤:

(1) 插桩被测程序, 对被测试程序的路径编码, 并对算法所需的控制参数赋值。

(2) 初始化种群。

(3) 解码进化个体, 作为输入运行被测试程序。

(4) 判断个体是否有穿越目标路径的, 若有, 保存与该进化个体对应的测试数据, 从目标路径中删除该路径。

(5) 判断是否满足算法终止条件, 若是, 转步骤 (7) 。

(6) 根据适应度函数计算进化个体适应值;实施选择、交叉和变异操作, 生成子代进化种群, 转步骤 (3) 。

(7) 终止种群进化, 解码进化个体, 输出测试数据。

2.5 对比算法—基于随机法的测试数据生成

在测试数据生成系统中, 随机法作为遗传算法的对比算法。与遗传算法不同, 随机法不采用进化操作, 每一代种群都是随机生成的, 且运行被测程序, 检查是否有穿越目标路径的测试数据, 如果有, 则记录该数据并删除找到的目标路径。如果生成了全部目标路径的测试数据, 或达到最大运行代数, 则终止算法。在系统界面管理模块中, 如果用户选择随机法生成测试数据, 可对算法的种群规模、最大运行代数, 以及实验次数等控制参数进行设置。随机法与遗传算法生成测试数据的具体步骤类似。

3 应用实例

3.1 系统用户界面

系统基于VC++6.0开发, 采用基于对话框的程序结构, 用户界面主要由菜单栏、参数设置区和文档区组成, 其中, 文档区由程序区、程序控制流程图显示区, 以及结果输出区组成。用户界面窗口显示分为4部分:左边为控制参数设置区, 中上方为程序区, 中下方为结果输出区, 右边是程序控制流程图显示区。

3.2 系统运行顺序

基于遗传算法的路径覆盖测试数据生成系统运行顺序:首先启动系统, 导入被测程序, 并根据被测程序的控制流程图选择测试路径;然后在系统界面中对算法的控制参数赋值, 对被测试程序的路径编码, 插桩被测程序;最后执行遗传算法, 生成测试数据, 并将结果呈现给用户。

3.3 在三角形分类程序中的应用

系统的实验环境:CPU P4、2.8GHz主频和1GB内存。采用三角形分类程序验证系统的有效性, 并将遗传算法和随机法生成的测试数据进行比较。插装后的三角形分类程序的C语言代码如图3 (a) 所示, 其流程如图3 (b) 所示, 图3 (b) 给出了路径的编码, 4条路径分别是:不能构成三角形的测试数据穿越的路径, 编码为1;构成非等边三角形的测试数据穿越的路径, 编码为01;构成等边三角形的测试数据穿越的路径, 编码为001;以及构成等腰三角形的测试数据穿越的路径, 编码为000。这样, 所有的路径可以编码为1 01 001000。

根据目标路径1 01 001 000, 在控制参数设置区分别给相应的参数赋值, 然后采用遗传算法和随机法各运行10次, 两种方法均使用随机产生的初始种群, 执行插装后的程序。实验过程中, 记录每次找到各路径的测试数据需要的进化代数, 并求其10次运行的平均值, 运行结果分别如图4和图5所示。运行系统, 找到全部4条目标路径的测试数据, 遗传算法需要的平均进化代数是21.20, 而随机法需要的平均进化代数是900.30, 前者仅是后者的2.35%。在进化时间上, 遗传算法需要的进化时间为0.016s, 而随机法需要0.641s, 前者仅是后者的2.50%。

4 结语

开发一种基于遗传算法的路径覆盖测试数据自动生成系统, 该系统能够根据用户选择的目标路径, 自动生成穿越该路径的测试数据, 提高了软件测试的效率, 节约了软件开发资源。该系统还存在不足之处, 如仅考虑了C或C++代码编写的被测程序, 被测程序的插装还不能够自动实现, 测试充分性准则还比较单一等, 需要进一步研究。

参考文献

[1]刘义, 万琳.C程序路径覆盖及测试数据自动生成系统[J].中国科教博览, 2005, 7 (1) :44-46

[2]陈继锋, 刘树锟, 王志海.面向路径的测试数据自动生成工具的设计[J].计算机工程与应用, 2010, 46 (15) :53-56

[3]周晓宇, 聂长海, 徐宝文, 等.两两组合覆盖测试数据自动生成集成工具的设计与实现[J].计算机科学, 2005, 32 (1) :118-119

[4]李宝林, 李志蜀, 陈良银, 等.面向路径的测试数据自动生成工具[J].计算机工程, 2007, 33 (15) :7-9

[5]严蔚敏.数据结构:C语言版[M].北京:清华大学出版社, 2002

数据结构课程设计-最小生成树 第2篇

设计题目：最小生成树

专业：xxxxxx 院系：计算机学院 姓名：xxxxxxxxx 学号：xxxxxx

时间：2013年10月7日

数据结构课程设计报告 最小生成树

目 录

一、设计目的……………………………………………………………….-2-

二、算法思想分析………………………………………………………-2-1.算法思想………………………………………………………………..-3-1）普里姆（Prim）算法思想……………………………………………………….-3-2）克鲁斯卡尔（Kruskal）算法思想..........................................-3-2.系统采用的数据结构和算法………………………………-3-

三、算法的描述与实现……………………………………………….-4-

四、用户手册………………………………………………………………-7-

五、总结…………………………………………………………………….-10-

六、参考文献…………………………………………………………….-10-

七、附录（源代码）………………………………………………...-10-

数据结构课程设计报告 最小生成树

1.算法思想

1)普里姆（Prim）算法思想

a)选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列；

b)在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列；

c)重复b)直到所有的节点出列。2)克鲁斯卡尔（Kruskal）算法思想

为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。

具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。

由于生成树上不允许有回路，因此并非每一条居当前最小的边都可选。从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通，由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。

2.系统采用的数据结构和算法 1)数据结构

Typedef int Vertextype;Typedef int adimatrix[MaxVertexNum][MaxVertexNum];Typedef int Vertextype vexlist[MaxVertexNum];Typedef int VexType;

数据结构课程设计报告 最小生成树

1.Great_adjmatrix()和Great_adjmatrix2()是两种建立图的方法；

2.克鲁斯卡尔算法（Kruskal）：

Void kruskal(GraphMatrix * pgraph,Edge mst[]){int i,j,min,vx,vy;int weight,minweight;Edge edge;for(i=0;i

n-1;i++){mst[i].start_vex = 0;Mst[i].stop_vex = i+1;Mst[i].weight = pgraph->arcs[0][i+1];} for(i=0;i

n-1;i++)//共n-1条边 {minweight = MAX;min = i;for(j=i;j

n-1;j++)//从所有（vx,vy）（vx∈U,vy∈V-U）中选出最短的边 if(mst[j].weight

for(j=i+1;j

n-1;j++)

数据结构课程设计报告 最小生成树

j=MST[k-1].endvex;//定位于权值最小边的尾顶点 for(i=k;i

4.out_edgeset()功能为显示最小生成树。

四、用户手册

1.运行程序，得到如下窗口：

2.输入顶点数，选择算法：

1）当输入的顶点数小于10时，选择Kruskal算法，如下图

数据结构课程设计报告 最小生成树

五、总结

该程序实现了在n个城市之间建设网络，既保证了连通性，也成为了最经济的架设方法。程序中应用了普里姆算法和克鲁斯卡尔算法，实现了矩阵的输出以及最小生成树的输出。不过，该程序仍有不足之处，图的输入数据过大，易出错，不易返回，仍需完善。

六、参考文献

[1]《数据结构程序设计题典》 李春葆编 清华大学出版社 [2]《数据结构（C语言版）》 严蔚敏 吴伟民编 清华大学出版社 [3]《数据结构课程设计》 苏仕华编 机械工业出版社

七、附录：（源代码）

#include #include #define MaxVertexNum 12 #define MaxEdgeNum 20 #define MaxValue 1000 #define MAXVEX 6 #define MAX 1e+8 typedef int Vertextype;typedef int adjmatrix[MaxVertexNum][MaxVertexNum];typedef Vertextype vexlist[MaxVertexNum];typedef int VexType;typedef int AdjType;typedef struct edgeElem edgeset[MaxVertexNum];

数据结构课程设计报告 最小生成树

{ scanf(“%d%d%d”,&i,&j,&w);GA[i][j]=GA[j][i]=w;//对称 } }

void Creat_adjmatrix2(vexlist GV,adjmatrix GA,int m,int e,GraphMatrix &graph){ int i,j,k,w,x,y;

printf(“输入%d个顶点序号(0-m-1)，序号从0开始。”,m);for(i=0;i=m){ printf(“您输入的序号有误，请输入0到%d-1之间的数，请重新输入。n”,m);scanf(“%d”,&GV[i]);} } for(i=0;i

GA[i][j]=MaxValue;printf(“请输入有多少条边。n”);scanf(“%d”,&e);printf(“输入%d条无向带权边（序号 序号 权值）：n”,e);for(k=0;k

数据结构课程设计报告 最小生成树

/* mst[min]是最短的边(vx,vy)(vx∈U, vy∈V-U)，将mst[min]加入最小生成树 */ edge = mst[min];mst[min] = mst[i];mst[i] = edge;vx = mst[i].stop_vex;/* vx为刚加入最小生成树的顶点的下标 */

for(j = i+1;j < pgraph->n-1;j++){ /* 调整mst[i+1]到mst[n-1] */ vy=mst[j].stop_vex;weight = pgraph->arcs[vx][vy];if(weight < mst[j].weight){ mst[j].weight = weight;mst[j].start_vex = vx;} } } }

void out_edgeset(edgeset MST,int e)//显示最小生成树 { int k;printf(“最小的消耗路线为n”);for(k=0;k

printf(“(%d %d %d)n”,MST[k].fromvex,MST[k].endvex,MST[k].weight);}

void prim(adjmatrix GA,edgeset MST,int n)//利用prim算法从0点出发求图的最小生成树

数据结构课程设计报告 最小生成树

int a;system(“color 71”);//改变屏幕颜色

printf(“ ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓n”);printf(“ ┃㊣ 必做题：最小生成树 ㊣┃n”);printf(“ ┃ 姓名：xxxx ┃n”);printf(“ ┃ 学号：xxxxxxxxx ┃n”);printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛n”);vexlist GV;//顶点表 adjmatrix GA;//边表 edgeset MST;//最小生成树 do{ printf(“输入图的顶点数n，我们将根据您输入的数据大小选择合适的算法。n”);scanf(“%d”,&n);if(n>=10)//大于10用prim算法来实现，否则kruskal算法来实现 { printf(“用prim算法从0点出发求图的最小生成树为：n”);printf(“请输入图的边数。n”);canf(“%d”,&e);Creat_adjmatrix(GV, GA, n, e);//创建图 prim(GA,MST,n);//生成最小生成树

面向路径的测试数据生成技术研究 第3篇

软件测试是在软件投入运行前, 对软件需求分析、设计规划说明和编码最终复审, 它是提高软件可靠性和保证软件质量的重要途径。通过软件测试, 可及时发现并纠正软件中存在的错误, 从而有效地避免软件投入使用后由于失效而造成的浪费。因此软件测试是软件开发的一个必不可少的环节。

软件测试可描述为对给定的程序P, 设P的输入空间为D, 且x∈D, 使P以x为输入运行, 从而找出P的错误和缺陷, 并对P加以修改和完善的过程。现有的软件测试分成静态测试和动态测试两类方法, 大多数软件测试方法都属于动态测试。根据测试数据生成的具体方法, 软件测试又可分为结构测试和功能测试。

测试数据生成问题Q可描述为对给定程序P和P中一条路径W, 设P的输入空间为D, 求x∈D, 使P以x为输入运行, 所经过的路径为W[1]。

求解问题Q的实质在于约束系统的建立和求解。建立约束系统的困难是分析、化简路径W上的各种语句成分和各种数据类型, 建立尽可能简洁的约束系统;求解约束系统的主要困难是处理可能存在的非线性约束。Weyuker等人的研究表明:不存在通用的有效算法, 对任意P和W, 能生成使W被经过的输入数据[2]。但实际应用的需要迫使人们进行研究, 并提出各种方法求解问题Q。

为解决这个问题, 本文将现有的求解方法分为随机法、静态法、动态法和试探法四类, 分析了每类有代表性的方法, 并指出了研究方向。

2、面向路径的测试数据生成方法

面向路径的测试数据生成的基本过程是根据一定的测试覆盖标准从程序中分离出相应的完整路径, 然后根据路径上判定条件和计算式等确定输入数据值。面向路径的测试数据生成方法主要包括随机法、静态法 (如符号执行法、区间算术法) 、动态法 (直线程序法、迭代松弛法) 、试探法 (遗传算法和模拟退火算法) 。

2.1 随机法

随机法是对程序输入空间进行随机取样, 其主要优点是生成单个测试数据的开销较小、简便易行。它可不受程序输入空间结构的限制, 迅速生成大量测试数据, 可用于功能测试。

D.Bird等采用随机法为PL/1优化与检查编译程序生成能完整执行并具备自检功能的PL/1程序[3]。但是该方法是盲目的, 具有很大的缺陷:为满足给定的测试准则, 生成的测试数据集通常都很庞大, 且有时很难满足某些特殊的测试要求。如随机法需产生二十多万组测试数据才使三角形分类程序达到分支覆盖。虽然可通过改进测试运行过程, 减少测试人员检查运行结果的数量, 但随机法仍无法避免庞大测试数据集的运行。

2.2 静态法

静态法采用符号执行等方法将路径上的所有 (判断) 语句转换成约束系统, 然后进行求解。静态法建立的约束系统包括面向路径的测试数据生成问题的全部解, 它主要包括符号执行和区间算术法, 它们都不适于功能测试。

2.2.1 符号执行

符号执行方法允许程序的输入不仅是具体的数值数据, 而且包括符号值。它建立约束系统的方式主要有两种:从前向后替换和从后向前替换。从前向后替换建立约束系统是将符号值作为程序输入, 执行所经路径上的语句, 将所经过的路径上各分支谓词用逻辑乘符号联结起来, 即得所需约束系统。在从后向前分析路径过程中, 记录分支谓词, 遇到赋值语句, 就将已记录的所有分支谓词更新。与从前向后替换方法不同的是, 从后向前替换方法无须保存各变量符号值, 但两者得到的约束系统相同。

2.2.2 区间算术法

区间算术法通过静态分析, 将经过路径上的所有语句转换成变量表和正则约束式表, 变量表保存经过路径上各语句定值或引用的所有变量, 包括常量和临时变量, 正则约束式表示变量间约束关系, 其形式为r=d1 option d2, 其中option是算术、关系或逻辑运算符, d1, d2是整型变量或常量, 正则约束式表中用指向变量表的索引表示变量r, d1, d2。

2.3 动态法

动态法从输入空间D中选一组数据x作为问题Q的一个解近似y (若y存在) , 运行程序P, 根据运行情况, 修改x值, 使之收敛于y。因程序运行时各输入变量值已确定, 故动态法可克服静态法一些缺点。但问题Q有解时, 动态法不保证总能找到。动态法可分为直线式程序法和Neelam Gupta等提出的迭代松弛法[4]。

2.3.1 直线式程序法

直线式程序法将路径W上的判断语句替换成形如A= (ci=0) 、A= (ci>0) 或A= (ci≥0) 的布尔型赋值语句, 将路径W上的语句转换成等价的直线式程序, 其中ci反映第i个分支谓词接近满足的程度。选择目标函数f, 使得若所有路径约束为真, 则f值为正数 (或0) ;否则为负数 (或0) 。问题Q转化为数值极大化问题:若f值为负数 (或0) , 则用数值优化方法极大化f, 直至其为正数 (或0) 。

2.3.2 迭代松弛法

迭代松弛法采用程序切片思想, 从输入空间D中任选一组输入考察路径W上各分支谓词, 通过静态、动态数据流分析确定各谓词函数对输入变量的依赖关系, 构造谓词片和动态切片, 建立这些谓词函数关于当前输入的线性算术表示, 然后建立输入变量的增量线性约束系统, 进而建立输入变量的增量线性方程系统, 求解后得到各输入变量增量, 从而获得一组新输入。

2.4试探法

试探法基本思想是从输入空间D中选择输入数据, 运行程序P, 根据结果, 结合概率思想产生新输入数据继续试探。试探法主要包括遗传算法和模拟退火算法, 可用于功能测试。

2.4.1 遗传算法

遗传算法采用编码技术将输入空间D映射到基因空间G, 并通过选择、杂交、变异等遗传操作和优胜劣汰的自然选择确定搜索方向。因采用种群方式组织搜索, 故可同时搜索G内多个区域。杂交和变异操作为种群引入新的信息, 从而更有利于找到全局最优解。

2.4.2 模拟退火法

模拟退火算法是在给定候选解的邻域选择候选解。关于目标函数更好的候选解总被接受, 但按一种受控方式接受恶化解, 其目的是使搜索过程从局部极值中摆脱出来。用控制参数控制是否接受恶化解。起初温度很高, 以允许在搜索空间几乎无限制地自由移动。在搜索过程中温度逐步降低, 限制对恶化解的接受。最终进入冻结状态, 不再接受恶化解, 搜索过程简化为简单爬山法。

3、结语

本文对近年来面向路径的软件测试方法作了简要的介绍与研究, 从目前的研究现状来看, 研究较多地集中在测试用例生成和结构测试中路径选择方法。虽然目前已经有了一些成熟的理论和成功的方法, 随着其应用领域的拓展和新兴技术的显现, 仍然需要不断的发展和完善。

随着软件技术的不断向前发展, 面向对象、软件体系结构、构件等新技术的应用为软件测试带来新的问题和挑战。基于面向对象和软件体系结构的软件测试方法是未来软件测试研究的重点;软件构件概念的提出为软件复用提供了技术基础。同时, 并发所引起的非确定性也给软件测试带来新的机遇, 软件测试技术将作为软件工程的一个重要分支蓬勃发展。

摘要：本文论述了面向路径的软件测试方法, 对测试中的路径选择和测试数据自动生成进行了分析, 着重研究了面向路径的测试数据生成中的区间代数、迭代松弛和遗传算法等方法, 最后指出了软件测试技术的发展方向。

关键词：软件测试,测试数据,区间代数,迭代松弛,遗传算法

参考文献

[1]单锦辉, 姜瑛, 孙萍.软件测试研究进展[J].北京大学学报, 2005;41 (1) :134-145.

[2]Weyuker E.J.The Applicability of Program Schema Results to Programs[C].Int J Computer Information Sciences, 1979;8 (5) :387-403.

[3]Bird D, Munoz C U.Automatic Generation of Random Self-checking Test Cases[J].IBM Systems Journal, 1983;22 (3) :229-245.

测试数据生成 第4篇

关键词：遗传算法,软件测试数据生成,应用研究

遗传算法具有一系列的优点,将其应用于程序的执行中,能够有效的解决测试数据生成中的相关问题,对于其实用化程度的提升具有积极的作用,本文就主要对遗传算法及其在软件测试数据生成中的应用予以简单分析研究。

1遗传算法的简单介绍

遗传算法是一种通用的搜索寻优算法,其主要依据自然选择原理与自然遗传机制,对自然界生命的进化机制予以模拟,以此来实现人工系统中某一个特定目标的优化工作,其工作原理如图1所示 :

通过上图可以看出其工作流程主要表现为 :通过编码使实际问题的参数集生成遗传算法识别过程中所需的位串形式,然后通过初始化处理生成初始种群,再对该种群开展反复的GA运算,其中包含了突变运算、交换运算与选择运算,直到通过适值运算之后得到合适的种群,然后通过解码获取解决实际问题所需的参数集,以便于实际问题能够得到解决或者改善。可以对遗传算法进行形式化的描述,表示为 :

上式中,Pinit表示的是初始种群,其中Pinit={P1,P2,,Pp},Pi表示的是种群的个体,是一个长度特定的二进制串,p表示的是种群规模分别表示的是遗传算法中的基本算子,其中为突变、为交换、为选择,有了这几个基本算子之后,就可以从一个初始种群出发,产生其他一些相关的期望改良的种群。

表示的是 评价个体 适应度的 函数,也就是通常所说的适值函数,其中 :

2基于遗传算法的软件测试数据生成系统及相关实例

在基于遗传算法的软件测试数据生成系统中,结构测试数据的系统模型的构建过程中,主要的搜索策略是遗传算法,该模型主要由三部分组成,即测试运行环境、遗传算法包、测试环境构造。其中,构造测试环境是整个软件测试数据生成系统的基础,其主要是借助于各种插装技术结合静态分析中所提供的基本单元信息来进行测试运行环境的构造,这其中包括桩模块、测试单元及驱动模块的构造,在该部分的构造过程中,还需要应用有用参数编码方案及符号执行技术生成相关的遗传算法的编码参数。

举一个典型的实例,下述代码是为了反映待测程序的一般性而设计的一段ADA语言程序单元 :

With TEXT_IO:use TEXT_IO;

Procedure TEST(PI:in out integer)is

Procedure UNIT01(P1:integer)is

X1:integer;

X2:float;

E:integer;

Procedure TEST_UNIT(I:in out integer:F:in FLOAT)is

O:integer;

Package INT_IO is new INTEGER_IO(INTEGER);

Use INT_IO;

Begin

PUT_LINE“(Please Input an integer below:”);

GET(0);

I:=1;

If O>0 and O<2 then

If F>3.0 and F<4.0 then

If E>0 AND E<50 then

PUT_LINE“(Condition matched!”);

End if;

End if;

End if;

End TEST_UNIT;

Procedure UNIT011(P1:in out integer)is

Begin

TEST_UNIT(X1,X2);

End UNIT011;

Begin

UNIT011(X1);

End UNIT01;

Begin

UNIT01(P1);

End TEST

这是一个非常典型的ADA语言程序单元,在后续的研究中,假设将代码中的TEST_UNIT作为待测单元,并对其中指定的全真分支路径实施探讨。

3基于遗传算法软件测试数据生成系统参数的选取及编码方案

在开展程序单元的结构测试时,其被测单元中,对于执行路径具有影响的参数的个数不是固定不变的,并且其类型也不统一,并且在应用遗传算法开展计算的过程中,其关注的重点是参数编码本身,是一种与问题无关的算法,所以在实际的应用中,要应用遗传算法,一个非常重要的问题就是参数的选取,以及应用何种参数编码方法。

在实际应用中,得到影响路径的编码主要有这几种 :(1)测试单元的入口参数,如在TESTUNIT单元中的I参数与F参数 ;(2)外部变量,对于TEST_UNIT单元来讲,E、X1、X2是其外部变量,在测试过程中,如果在测试单元中应用了外部变量,就应该考虑是否需要开展编码 ;(3)通过I/O输入的变量,例如 :指定单元中的变量O。本次研究中,只对与测试单元相对应的测试路径条件表达式相关的变量开展编码,对于TEST_UNIT单元中的全真分支路径,依据有用参数编码的基本原则,从中选择O、E、F几个参数变量开展编码。并对I/O输出予以单独处理,这主要是因为输出语句的存在对于遗传算法的执行效率具有严重的影响,而其不会影响到程序的执行路径,所以可以应用空语句来进行替换。

对于输入语句来讲,应用输入重定向技术将变量的输入从I/O定向为一个充当I/O的I/O变量,将输入语句转化为赋值语句,然后对转化之后的赋值语句开展相应的分析处理,通过这种转换调整之后,所选取的参与编码的变量就为IOVAR、F、E。

在相关问题的求解过程中,遗传算法要求将问题的解空间表示为在某一个有限字母表上的有限长度的串,所以在应用遗传算法生成相关测试数据时,要选择合适的映射方式f,以便于被测程序的输入参数能够表示成为一种适当的编码形式,在选取从参数值到编码的映射f的过程中,应该遵循下列的基本原则 :(1)输入参数所取得的所有值都应该具有唯一的编码 ;(2)任何一个编码都应该具有唯一的参数值与之相对应 ;(3)要选取能够使问题得到自然表达的最小字母表来开展编码 ;(4)所选择的编码方式应该与问题自身具有较大的相关性。

为了满足上述基本原则,在实际应用中,可以建立起字母表 {0,1} 以上的十进制编码,该种编码方式具有操作简单、易于表达的优点,能够促进遗传算法计算的高效开展,在实际应用中,由于输入参数的数据类型具有较大差别,并且不同类型的参数具有各种不同的编码映射,当输入多个参数时,应该先将每个输入参数单独编码成二进制位串,再将所有的位串进行连接,以便于形成一个个有效的个体,将其称之为多参数级联编码。如图2所示 :

4适值函数

遗传算法与实际问题的接口就是适值函数,所以,应该注意适值函数的构造与实际问题之间的联系,在分支函数的正向叠加法中,分支函数作为分支谓词到实值的映射,就是一个实值函数,可以将其量化的反映到测试数据的驱动之下,被测单元的实际执行路径对于所选定路径的覆盖程度,对于分支函数的插装,可以通过J.C.Huang所提出的程序插装理论来进行插装,在选定路径上的各个分支点前插入相应的分支函数。相关的实践研究表明,通过分支函数正相叠加法所生成的适值函数,能够对测试数据的优劣予以准确的反映,并且能够引导遗传算法找到最终的目标参数值。

在单元测试过程中,主要有自底向上与自顶向下两种测试方法,其中自底向上的单元测试方法主要是从最底层依次向上开展的单元测试,在这种测试方法中,需要为其构造与其相对应的驱动模块。其中Ada是一种层次型的语言,是一种语序嵌套结构,在其测试过程中,一种常用的测试方法为DTA测试法。

5结束语

测试数据生成 第5篇

其中遗传算法与其他传统的优化搜索算法相比，以生物进化为原型，具有良好的全局搜索能力、收敛性好、计算时间少、鲁棒性高等特点。所以在解决实际优化问题上，遗产算法是最有效的优化算法之一。本文以遗传算法为核心，对遗传算法的自改进和与其他智能优化算法混合改进在软件测试数据自动生成方向的应用进行详细的探讨。

1 软件测试数据自动生成的概述

软件测试数据自动生成分为功能测试(黑盒测试)数据生成和结构测试(白盒测试)数据生成。从现有文献看，功能测试数据生成方法包括边界值法、等价类划分法、决策表法、因果图法、功能图法、错误推测法、正交实验方法等。结构测试数据生成方法包括随机测试数据生成方法、面向目标的测试数据生成方法、面向路径的测试数据生成方法、基于遗传算法的结构测试数据生成方法。功能测试数据生成是按照需求规格说明设计测试数据的方法，测试简单，完全不考虑程序内部结构和内部特性。结构测试数据生成只根据程序的内部结构设计测试数据。在规划测试时，将两者结合起来应用，加入其他的智能算法是帮助测试数据生成的一个发展方向。

2 应用于测试数据自动生成的自改进遗传算法

2.1 遗传算法简介

遗传算法模拟自然选择和自然遗传过程中发生的繁殖，利用遗传算子(选择、交叉和变异)对个体进行组合，产生新一代候选解，重复此过程，直至满足某种收敛指标。遗传算法直接对结构对象进行操作，具有很强的鲁棒性;隐并行性和更好的全局寻优能力;采用概率化的寻优方法，自动获取、指导优化的搜索空间。鉴于遗传算法的这些优点，人们将其广泛应用于图像处理、自动控制、机器学习、模式识别和人工生命等领域，成为现代智能计算中的关键技术。

2.2 遗传算法自改进的策略研究

遗传算法的种群规模较大，迭代分析次数过多，导致运行时间长，且易受参数影响;此外还易出现早熟和局部搜索能力弱等现象。所以，为适应具体需求对遗传算法进行改进，改进的过程可以体现在算法的各个步骤。遗传操作算子(选择、交叉、变异)三种基本形式构成了遗传算法强大搜索能力的核心，是模拟自然选择和遗传过程中发生的繁殖、杂交和突变现象的主要载体[1]。

2.2.1 选择算子的改进

基本遗传算法的选择算子是基于个体的适应度来选择进入下一代群体中的个体。常用的选择方法：轮盘选择法，排序选择法，最优个体保存法等。其中最常用的是最优个体保存，它可以保证遗传过程中所获得的较优个体不会被交叉和变异操作破坏。文献[2]在介绍经典选择算子的基础上结合文献分析选择算子的改进，为遗传算法中选择算子的选取提供相关的策略。此外在遗传算法运行的初期，群体中可能会有少数几个个体的适应度非常高，这些个体被选择的概率非常大，这时交叉操作就起不了什么作用，造成群体多样性降低，容易导致遗产算法早熟。为了克服这种现象，文献[3]提出了一种新的适应值变换方式:适应值标度变换，即适应值远离群体适应值均值的个体被选中的0概率高，处于中间未知的个体对群体改进的贡献小，选中概率低，这样有助于改进群体的多样性。此外还有许多种选择策略，比如文献[4]提出的基于个体差异的局部竞争选择算子，文献[5]提出的基于竞争指数的模拟退火排序选择算子。文献[6]提出采用多代竞争遗传算法思想，即选择过程由上代种群、本代种群和经过交叉和变异算子作用过的染色体种群共同竞争。文献[7]提出了过滤操作，即进化过程中，用较优个体代替较差个体，以减少有效基因的丢失，改进算法性能。

2.2.2 交叉算子的改进

交叉操作是指两个相互交叉的染色体按照某种方式交换其部分基因，从而形成两个新得个体的过程。常见的交叉方法：单点交叉，两点交叉，多点交叉，均匀交叉，算术交叉等。文献[8]对遗传算法中较成熟的交叉算子进行了简单介绍，在此基础上结合文献内容，从理论应用以及作用机理等几个方面对遗传算法中改进的交叉算子做了梳理。此外，还可以考虑如当初始种群采取二进制编码，采用多点交叉时，初期将交叉点均匀落在每个参数的位串，但考虑较优个体随机位应尽量设置为权值较低位。文献[3]提出了在算法运行一段时间以后，群体向搜索空间中包含较优解的区域收敛，这时群体中会存在较多相同的染色体，传统的交叉算子可能失效，算法容易形成早熟，针对这样情况可用自交叉算子。文献[9]提出了可限定适应值高的个体按照某种交叉规则互相交叉，从而快速得到“更优”。文献[7]提出了可采用交叉操作概率为动态参数选择，将交叉概率值与适应度值的变化联系，群体初、中期采用较大交叉概率，中、后期采用适中的交叉概率，后期采用较小的交叉概率，在某种程度上可避免陷入局部最优的局面，以增强局部搜索能力。文献[10]设计了一种拉普拉斯交叉算子，利用拉普拉斯分布函数，使子代群体能自适应父代群体的变化。

2.2.3 变异算子的改进

变异是指个体染色体编码串中的某些基因用其他等位基因来替换，从而形成新的个体，从而改善遗传算法的局部搜索能力，维持种群多样性，防止早熟。常见的变异方法:基本位变异，均匀变异，二元变异，高斯变异等。文献[11]提出了在遗传算法初期运行阶段较多用到均匀变异，可增加群体多样性，但要考虑到优势个体进行较小变异，劣势个体进行较大变异。此外同交叉操作，变异操作概率亦可采用动态参数选择。文献[7]提出了对于初期的种群而言，交叉几乎可以等效于一个非常大的变异率，而过大的变异率可能影响进化过程。变异算子和交叉算子的相互配合，将更好的完成对搜索空间的全局和局部搜索，最终使得遗传算法以最佳的搜索性能实现最优化问题的求解过程，同时提出了大变异操作，使用远大于通常的变异概率进行一次变异操作，可随机、独立生成许多新个体，避免早熟。

2.2.4 其他要素设定

根据遗传算法的操作过程，遗传算法的其它关键和难点主要包括：编码方式，初始种群规模的设定，适应度函数、终止条件的设计，遗传算子的参数设定，对此很多学者进行了系统的研究，这里不做讨论。

2.3 相关实例

文献[12]设计选择算子采用多代竞争遗传算法，交叉算子采用均匀交叉;变异算子的变异概率与动态的参数联系，适应度函数采用分支函数叠加法，通过典型的三角形分类程序进行测试数据的生成，证明了自改进遗传算法的有效性，在一定程度上降低算法的过早收敛性。文献[3]设计选择算子采用非单调适应值标度变换方法，交叉算子采用自交叉操作，变异概率的取值与当前群体的最佳个体的适应值的变化联系，适应度函数采用分支函数叠加法，将改进后的算法应用于一段程序测试路径的生成，可以发现自改进遗传算法避免了路径搜索过程的盲目性，搜索效率极高，在测试用例生成这一类随机搜索问题上成为强有力的搜索算法。文献[13]提出了一种利于被测程序结构信息来指导交叉、变异操作的改进行遗传算法，并将其应用到面向路径的测试数据生成当中，实验数据表明此算法与传统遗传算法相比降低了迭代次数，缩短了生成测试数据所需的时间，提高了测试数据生成的效率。

3 应用于测试数据自动生成的混合算法

3.1 粒子群遗传混合算法

粒子群算法[14],1995年由Kennedy与Eberhart两位学者所提出，粒子群算法的理论基础是以单一粒子作为鸟类族群之中的单一个体，于算法中赋予该粒子(个体)记忆性，并能够透过与粒子群体中的其他粒子之间的互动而寻求到最优解。粒子群优化具有相当快的逼近最优解的速度，可以有效的对系统的参数进行优化，可以与遗传算法混合，以此实现优势互补。简单的混合算法如用遗传算法来初始化粒子群算法的初始种群，或者用粒子群算法来初始遗传算法的初始种群。但文献[15]证明，前者的策略只能获得一点性能的提升，后者则没有一点性能的提升。文献[16]中提出从粒子群算法中结合了标准的速度和位置更新，同时从遗传算法中继承了选择、交叉和变异等操作，增加了一个参数来决定测试集合中能进行选择、交叉和变异操作的比例。文献[17]提出了以粒子群算法为主线，按粒子群算法中标准的速度和位置更新，并将遗传算法的选择、交叉、变异与粒子群算法的自动更新特性结合，交叉概率为动态参数确定，利用高斯算子进行变异。实验以三角形程序段的全部if语句路径为测试对象，由实验结果得出与传统遗传算法相比，收敛速度更快，精度更高。文献[18]结合遗传算法和粒子群算法的思想和各自的特性形成新的混合算法，并构造此算法的测试数据自动生成的模型;测试实例采用常用测试函数Rastrigin证明混合算法的寻优能力更强，采用三角形类型判别程序，验证新算法在路径测试数据的自动生成的应用，无论在迭代次数和运行时间上都比遗传算法有较大改进。

3.2 蚁群遗传混合算法

蚁群算法[19]是一种基于种群的模拟进化、用于解决复杂优化问题的全新的启发式算法，通过对候选解组成的蚁群的进化来寻求最优解。算法由许多蚂蚁共同完成，每只蚂蚁在候选解的空间独立搜索解，在所寻得的解上留下一定的信息素，并且感知其他蚂蚁释放的信息素，倾向于选择信息素浓度较高的节点。蚁群算法具有摆脱局部最优点的能力，能抑制遗传算法的早熟现象。文献[20]针对遗传算法在搜索初期具有较高的速度向最优解收敛，但某时间点后效率明显降低，蚁群算法在搜索初期由于信息素信息缺乏，搜索速度较慢，但当信息素累积到一定程度后，向最优解收敛的速度迅速提高，提出了搜索初期采用遗传算法生成初始信息素分布，之后则采用蚁群算法求解最优解。此改进算法需在遗传算法迭代过程中比较个体适应值的变化，以确定遗传算法和蚁群算法的最佳融合时机。实验基于某测试用例库，结果表明利用遗传蚁群融合算法在进行测试用例最小化，在时间效率和最小化规模都优于遗传算法和蚁群算法。文献[21]从参数编码、信息素更新、适应度函数以及蚂蚁路径的交叉和变异等方面做出了一定的改进，实验部分通过在Linux系统下某联通BBS系统的信控触发程序软件测试用例自动生成来验证遗传蚁群算法再生成测试用例的优劣性。实验结果显示出遗传蚁群算法在生成测试数据的过程中，前期可以通过遗传算法将蚂蚁路径上的信息素初始化，提高搜索效率，在后期路径变异，增加全局收敛性，使其具有比遗传算法更高的测试数据生成效率。借鉴遗传算法的交叉原理，文献[22]提出首先通过蚂蚁搜索来得到代表不同输入域组合的路径，再对路径进行交叉重组，从而得到新的输入域的组合，充分发挥蚁群算法在路径寻优方面的优势，提高了测试数据生成的多样性，进而减少了冗余数据的生成。

3.3 模拟退火遗传混合算法

模拟退火算法[23]是1982年由Kirkpatrick等提出的一种随机搜索算法，模仿力学中固体的退火过程。模拟退火算法运用温度参数进行控制，在温度较高时接受较差解的概率大，随着温度逐渐降低接受较差解的概率逐渐趋近于0，因此具有较强的局部搜索能力，将模拟退火算法和遗传算法结合能弥补遗传算法过早陷入局部最优解的局面。退火遗传算法使解空间维持多样性，在进化过程中随着退火过程温度的不断降低接受劣质解的概率也逐渐降低，从而在一定程度上避免遗传算法陷入局部最优，使其更好地找到最优解。文献[24]提出了将模拟退火操作引入遗传操作的方法是在遗传算法执行过程中的交叉、变异操作后对新产生的解进行模拟退火操作，使新产生的解和父代以一定的概率被接受。遗传算法初始种群编码为二进制编码，同时对遗传算子进行自改进：动态调整交叉概率和变异概率，适应度函数采用基于分支距离[25]的方法。实验部分采用软件测试领域得到广泛应用的判断三角形的程序，验证了模拟退火算法的有效性，该方法以更短的时间获得更高的代码覆盖率。文献[26]设计了在标准的遗传算法中融入模拟退火的思想，基本思想同上，适应度函数采用“分值函数叠加法”。实验部分采用某系统的部分代码，采用C++语言进行算法的编程实现，应用混合算法最终可较快地找出合适的全局最优解。和传统遗传算法相比，可有效避免早熟问题，加快了遗传进化速度，提高了测试数据自动生成的效率。文献[27]介绍了针对遗传算法易早熟，将模拟退火的思想引入遗传算法的几种混合方式，并对其进行了简单的性能评价，选取将模拟退火算法的Boltzmann机制引入遗传算法，即按照一定的概率接受比父辈差的染色体。此外算法采用“多参数级联编码”[28]，均分多点交叉，仅对染色体位串末几位进行变异，基于“分支函数”思想的适应度函数，通过经典的三角形问题验证此算法效率明显提高。

3.4 禁忌搜索遗传混合算法

禁忌搜索算法的思想最早由Glover在1986年提出[29,30]，是对局部领域搜索算法的推广，是模拟人的思维的一种智能搜索算法。禁忌搜索算法在搜索的过程中可以接受劣质解，故具有较强的爬山能力，搜索时能够跳出局部最优解，转向解空间的其它区域，从而增强获得更好的全局最优解的概率，并且具有灵活的记忆功能和藐视准则。因此可将遗传算法和禁忌搜索算法进行结合，从而弥补遗传算法的不足。H Mublenbein[31]是最早把记忆功能引入到遗传算法中，而禁忌搜索算法的创始人F.Glover在文献[32]提出了遗传算法和禁忌搜索算法相混合的理论基础。文献[30]对遗传算法与禁忌搜索算法从广义的范围进行分析和比较，但并未提出具体的混合优化策略算法。文献[33]在文献[32]的基础上，把禁忌搜索引入到遗传算法进行搜索过程中：把禁忌表作为遗传算法的变异算子和交叉算子，从而改善遗传算法爬山能力弱的缺陷。文献[34]提出利用遗传算法提供并行搜索主框架，结合遗传群体优化和禁忌搜索极强的具有避免迂回搜索能力的邻域搜索，实现快速全局优化，遗传禁忌模型的算法程序包基于Java语言实现。采用“判断一个三角形是否为等腰三角形”的程序对算法的性能进行分析，并且使用遗传禁忌算法、随机法和遗传算法进行比较，分析得到所提出的算法在性能方面相对最优。文献[35]在遗传算法的基础上，引入禁忌搜索算法，提出了一种面向对象测试用例自动生成的方法。该方法设计了一种新的类对象编码方式，并在此基础上构造了类测试用例自动生成所需的适应度函数，使每一个测试用例在局部区域中再次寻找最优值，从而改进整体算法搜索最佳值的能力。实验结果表明，该方法结合遗传群体优化和禁忌搜索较强的爬山能力，能够实现快速全局优化，自动生成高质量的测试用例。

3.5 与其他算法混合改进策略

遗传算法除与上述四种启发式随机搜索算法融合，也已经与文化算法、量子算法、免疫算法、神经网络算法等有效结合。

4 结论

测试数据生成 第6篇

1 测试驱动开发

测试驱动开发的理念强调把测试作为开发过程的一个重要部分, 在软件开发的每一个阶段, 都有一部分的设计和代码是专门给测试使用的。甚至在代码开始编写之前, 测试用例就已经设计好了。将测试方案作为编码的准绳, 从测试的角度验证设计, 推导设计, 指导编码。实时验证系统的准确性。下面具体结合状态图, 介绍一个企业通信系统的测试驱动开发过程。

2 状态图模型和状态图中的变迁约束规则

2.1 状态图定义

状态图形式化地表示为一个五元组K〈S, ∑, T, S0, F〉, 其具体含义可参见文献[3]。

2.2 基于前后事件约束规则CSPE:

基于前后事件约束规则:CSPE约束 (Constrains on Succeeding and Preceding Events) , 用于限制在某一事件后发生其它事件的可能性, 它规定了前后事件之间的依赖关系, 但是忽略了程序运行时的具体状态。它的定义与规则参见文献。

2.3 基于状态图的前后事件约束规则S-CSPE:

基于状态图的前后事件约束规则S-CSPE (statechart-CSPE) , 是对CSPE的一种有效的扩展, 它将事件约束限制在状态的控制之下, 并且引入了超态的概念。使得对前后事件约束的依赖关系描述的更加准确, 并且增加了测试用例的可执行性。

t1∈T (S1) , t2∈T (S2) , 其中α、β、γ为任一变迁序列, β、γ满足:如果t’∈β、γ, 则t’/∈T (S1) ∪T (S2) 。

规则定义D (C) :n’[t1;t2]C (C≠FALSE) 该规则含义:如果α.t1是有效前缀序列, 则必存在使C为真的β, 使得α.t1.β.t2为有效前缀序列;且对于任意t (t∈T (S2) ) , 任一使C为真的γ都使得α.t1.γ.t为无效前缀序列。

规则定义E (C) :a’[t1;t2]C (C≠FALSE) 该规则含义:如果α.t1是有效前缀序列, 则必存在使C为真的β, 使得α.t1.β.t2为有效前缀序列;且对于某一t (t∈T (S2) ) , 必存在使C为真的γ, 使得α.t1.γ.t为有效前缀序列。

规则定义F (C) :_’[t1;t2]C (C≠FALSE) 该规则含义:如果α.t1是有效前缀序列, 则对任一在使C为真的β都使得α.t1.β.t2为无效前缀序列。

3 关于测试路径覆盖标准的定义

3.1 测试路径的定义

D (t) :变量V的集合, V出现在变迁t的赋值语句的左侧或者输入语句部分。

C_USE (t) :变量V的集合, V出现在变迁t的赋值语句的右侧或者输出语句部分。

P_USE (t) :变量V的集合, V出现在变迁t的谓语表达式中。

清晰定义路径 (D_Clear PATH) :路径 (ti, t1, , tm, tj) (m≥0) , 如果V/∈D (nl) (l=1, , m) , 那么满足该条件的路径为的清晰定义路径 (从ti到tj) 。

完全路径 (COMPLETEPATH) :一条满足约束集R的路径, 其初始节点是组合初态, 终节点是可接受组合终态。

3.2 基于状态图的前后事件约束规则 (S-CSPE) 的路径覆盖标准:

P是状态图S的完全路径集合, R是S的基于状态图的前后事件约束集:

all-D_CLEAR PATHs标准:对每一个变迁t的每一个V, V∈D (t) , P包含每一条关于V的D_CLEAR PATH。

4 测试用例实际生成研究

4.1 实例:

企业通信软件中一组通信模块的状态图 (图1) 表述

4.2 关于D_CLEAR PATH (清晰定义路径) 的生成

t11到t12的部分D_CLEAR PATH, 表1。

4.3 关于Complete Path (完全路径) 的生成

覆盖D_CLEAR PATH:t11 t3 t4 t12的部分完全路径集, 表2。

5 使用S-CSPE约束的优势

基于状态图的前后事件约束规则S-CSPE约束的D-use路径覆盖策略要求完全路径集必须覆盖所有的D_CLEAR PATH, 这保证了该D_CLEAR PATH将覆盖所有变迁, 这比基于前后事件约束规则CSPE有更强的路径覆盖能力, 而且该覆盖标准更方便实现TDD, 使测试用例自动生成。

6 结论

本文讨论的基于TDD结合状态图的测试方法兼顾了测试路径的覆盖力和测试用例爆炸的问题, 在保证一定覆盖能力的情况下, 避免了过多无效测试用例的产生, 从而提高了测试用例生成的效率。在公司一个Scrum小组实践应用, 产品发布周期缩短了10%, 而且客户bug反馈降低了50%。

摘要：介绍测试驱动开发 (TDD) 并结合状态图进行测试路径生成, 在避免了测试路径过多的情况下保证了测试路径的覆盖率。

关键词：TDD,状态图,路径覆盖策略

参考文献

[1]测试驱动开发 (美) Kent Beck著[M].北京:中国电力出版社, 2003.

[2]Robert V.Binder.面向对象系统的测试[M].北京:电子工业出版社, 2001.

[3]乔木, 曾一, 林宏.状态图的并发状态约束及测试用例生成研究[J].计算机工程与应用, 2004.

基于面向服务的测试用例生成研究 第7篇

该文首先通过对WSDL文件各数据类型进行分析, 通过逐步遍历并解析提取关键节点生成T模型;其次依据T模型中的各节点间的关系通过等价类划分、边界值等方式生成根节点的测试数据;最后通过对WSDL文件中服务的操作序列进行排序,从而可通过结合操作序列及测试数据生成测试用例,通过执行各测试用例并查看结果是否满足需求规格说明中规定的功能来验证服务的有效性。

1 WSDL数据类型模型化

WSDL中的Types是一个数据类型定义的容器,包含了所有在消息定义中需要的XML元素的类型定义[6]。数据类型包含3种:内置类型、简单类型和复杂类型。 内置类型由XML Schema定义,常用的内置类型包含: 字符串型、小数型、整数型、布尔型、日期型及时间型;简单数据类型由用户自定义,在WSDL中通过<xs:simple- Type>来标志元素为简单数据类型,简单数据类型可通过在内置数据类型中增加restriction或者在其他简单数据类型(list,union)中获取;复杂数据类型通过<xs: complex Type>标志元素为复杂数据类型,通过关键字sequence,choice及all定义子元素出现的方式。若为sequence,复杂类型元素的子元素必须按定义的顺序出现;若为choice,复杂类型元素的所有子元素只能出现一个;若为all,复杂类型元素结构中的子元素可以任一顺序出现。

简单数据类型节点间的约束及内置数据类型的约束条件包括边界约束及非边界约束。 边界约束为: max Length,min Length,max Inclusive,min Inclusive,total-Digits,fraction Digits;非边界约束包括:pattern,enumera-tion。复杂数据类型结构体中父元素与子元素的限制条件为:max Occurs,min Occurs,unique,use,nillable。

将WSDL中的数据类型模型化用树状模型来表示:

T=<R,N,D,IC,RC,EE,ED>

其中:R为数据类型的根节点;N为复杂数据类型的子元素、子元素属性及复杂数据类型的关键字集合; D为S ⋃ B,S为简单数据类型节点集;B为内置数据类型节点集;IC为R ⋃ N与N间的约束关系;RC为R ⋃ N ⋃ D与D间的约束关系;EE为R ⋃ N节点与N节点的边的集合,EE={p,x,c},p(R⋃ N)为父节点,c∈N为子节点,x∈IC为父节点对子结点的约束;ED={p,x,c},p∈(R ⋃ N ⋃ D)为父节点,c∈D为子节点,x∈RC为父节点对子结点的约束。

算法如下:

输入WSDL中元素类型的定义,输出WSDL中元素类型的T模型。

Step1:模型元素初始化:R=∅ ,N=∅ ,D=∅ ,IC=∅ ,RC=∅ ,EE=∅ ,ED=∅ 。

Step2:查看WSDL文件中的首个数据类型n,令R={n}。

Step3:如果节点n的数据类型为复杂数据类型,转入Step4; 若节点n的数据类型为内置数据类型,转入Step5;若节点n的数据类型为简单数据类型,转入Step6。

Step4:解析WSDL文件,T模型的下个节点为m,m应为se- quence,choice,all之一,树状模型各元素此时变为:N=N⋃ m,x=∅ ,IC=IC⋃ x,EE=EE⋃(n,x,m)。令n=m;遍历WSDL文件中复杂类型的子元素,产生新节点m,x此时为子元素在复杂数据类型中出现的最大次数与最小次数,默认值为1,树状模型各元素测试变为:N=N⋃ m,IC=IC⋃ x,EE=EE⋃(n,x,m)。令n=m,返回Step3。

Step5:解析WSDL文件,T模型的下个节点为m,若x为内置数据类型的默认约束条件,树状模型各元素此时变为:B=B⋃ m, RC=RC⋃ x,ED=ED⋃(n,x,m)。

Step6:解析WSDL文件,T模型的下个节点为m,若m为re- stricton内置数据类型,x为内置数据类型的人为约束条件,则树状模型各元素此时变为:B=B⋃ m,RC= RC⋃ x,ED=ED⋃(n,x,m)。

若m为restriction简单数据类型,x为简单数据类型的人为约束条件,则树状模型各元素此时变为:S=S⋃ m,RC=RC⋃ x,ED=ED ⋃(n,x,m)。令n=m,返回Step3。

若m为list数据类型,x为父节点对列表的限制条件,则树状模型各元素此时变为:S=S⋃ m,RC=RC⋃ x,ED=ED⋃(n,x,m)。 令n=m,返回Step3。

若m为union简单数据类型,则树状模型各元素此时变为:S= S ⋃ m,x=∅ ,ED=ED⋃(n,x,m)令n=m,遍历每个成员类型,转至Step3。

在某网络管理系统测试项目中,wsdl部分源码如下:

生成的T模型如图1所示。

2测试数据生成

测试数据生成步骤:

(1)依据T模型中的D=SB集合及约束面IC,生成内置数据类型的测试数据集;

(2)建立T模型中节点间的依赖关系;

(3)依据依赖关系生成根节点的测试数据。

2.1获取内置数据类型及简单数据类型中的测试数据

方法:遍历B集合中的每个节点,若此节点的父节点为N,则依据父节点对此节点的约束条件,依据等价类划分及边界值法生成有效测试数据及无效测试数据; 若此节点的父节点为S,则重复遍历父节点的父节点, 直到父节点为N为止,依据所有的约束条件,通过等价类划分及边界值法生成有效测试数据及无效测试数据。

算法如下:

输入:T模型树,T=<R,N,D,IC,RC,EE,ED>。

输出:B_Test Data,内置数据类型的测试数据。

Step1:遍历T模型中集合B中的节点m及边e(n,x,m),如果n∈(R⋃ N),转至Step3,若n∈S,取边y=∅ ,转至Step2(x,y为父节点对子节点的约束)。

Step2:遍历T模型中集合e(o,x,n),若x≠∅ ,令y=y⋂ x, m=n,n=o,如果n∈(R⋃ N),转至Step4,否则继续Step2。

Step3:依据约束条件x,根据等价类划分、边界值及随机取值方法生成节点m的测试数据。

Step4:依据约束条件y,根据等价类划分、边界值及随机取值方法生成简单类型节点m的测试数据。

2.2建立T模型中节点间的依赖关系

方法:找出根节点与底层节点的关系,底层节点的测试数据在2.1已求出,从而依据底层节点的测试数据可求出根节点的测试数据。

算法如下:

输入:T模型树,T=<R,N,D,IC,RC,EE,ED>。

输出:T模型树中节点间的依赖关系R。R=∅ ,temp=∅ 。

Step1:查看根节点m及根节点所在的边e(m,x,n),若e(m, x,n)∈EE,转入Step2;若e(m,x,n)∈ED,转入Step5。

Step2:若n节点为sequence节点,若n节点为all节点,转至Step3;若n节点为choice节点,转至Step4。遍历n节点作为父节点的边e(n,x,ci),取ki=Random(min Occurs,max Occurs),得。令ci=m,转至Step1。

Step3:遍历n节点作为父节点的边e(n,x,ci),取ki=Random(min Occurs,max Occurs),得。令ci=m,转至Step1。

Step4:遍历n节点作为父节点的边e(n,x,ci),取ki=Random(min Occurs,max Occurs),得。令ci=m,转至Step1。

Step5:R=R⋃ n,n为内置数据类型或者简单数据类型,在此称n为叶节点,测试数据可由2.1节的算法求得。

Step6:由Step1~Step5可知,根据节点与节点间的连接关系,通过层层迭代,可求得根节点与叶节点的关系。

由以上算法知,依赖关系无非是以下几种形式的嵌套:

m→ci,ci为内置数据类型或者简单数据类型,m_TD(节点m的测试数据)依据2.2节算法求得。

m→sequence(k1·c1,k2·c2,kn·cn)。ci为m的子节点,ki为节点ci的发生次数,ki·ci的测试数据生成为:的笛卡尔积。。

m→choice(k1·c1,k2·c2,…,kn·cn),m_TD=TD(ki·ci)。

m→all(k1·c1,k2·c2,…,kn·cn),因为all为节点的任意顺序,每一个顺序出现对服务的结果是一致的,故取测试数据为:。

3产生操作序列

WSDL中的Port Type定义了一种服务访问入口的类型,即传入/传出消息的模式及格式。一个Port Type可以包含若干个Operation,而一个Operation则是指访问入口支持的一种类型的调用,Operation中指明了服务所接收的input message及服务的output message,但并未指明服务操作的先后依赖顺序,本文通过在WSDL中对每个操作增加前置操作及后置操作,从而产生测试的操作序列。扩展前的WSDL Operation格式为:

算法如下:

输入operation元素,输出服务操作序列Operation Sequence。

Step1:输入operation元素,查看operation元素中前置操作是否为空,若为空,转入Step2;若不为空,转入Step3。

Step2:Operation Sequence.add(operation),查看operation元素中后置操作是否为空,若为空,结束并输出Operation Se- quence;若不为空,operation=nextoperation,转入Step2。

Step3:operation=preoperation,转入Step1。

4测试用例生成

综上所述,已经知道测试数据的生成方法与服务提供操作流方法,下一步只需将测试数据放置到opera-tion中即可,再将此用例放置到soap消息中,发送至被测软件,便可对服务进行自动化测试。通过人工查看服务对每个测试用例的响应结果是否与软件需求规格说明规定的响应结果一致,若一致,则此用例通过;若不一致,通过对服务进行分析,查找不一致的原因,对待测软件进行修改,并重新执行该用例,保证服务响应结果与软件需求规格说明保持一致。

5结语

数据报表的生成方法 第8篇

关键词：报表生成,查询,分析

1 需求概述

报表的生成系统的设计,对提升企业及时分析财务状况和经济效益的能力具有很重要的意义。报表的生成是从企业数据库中抽取相关数据,根据这些数据生成报表,方便用户对报表中的数据进行查看和分析,这些数据包括静态数据和动态数据,针对这一问题我们给出了解决方案和相应的程序设计。查询报表是根据具体业务需求,通过预先定义模板,动态获取业务数据,显示给用户查看,如需编辑需要导入excel进行编辑。

2 实现方案

目前报表部分的功能基本借助于华表插件(控件)来实现完成。

查询报表实现方式如下。

使用手动方式预先通过xml定义好报表显示模板,然后通过后台动态获取业务数据进行填充。

支持交叉表(也就是部分列可以根据后台动态生成)。

支持公式计算,可以借助华表按照指定公式进行行计算,列统计目前通过后台实现。

支持分组统计,对一张报表中的数据可以按照不同的字段进行统计,需要预先定义好。

2.1 报表种类

2.1.1 按编制方式分为:

固定表和浮动表

(1)固定表:固定行和列的表,用户在定义模板时必须定义最大行列区域内的所有单元格的指标。

(2)浮动表:行浮动或列浮动或行列均浮动的表。

2.1.2 按是否同任务分为:

不同任务表和相同任务表

(1)不同任务表:可能表套不同或期间不同的表,可能是固定表或浮动表,这类表又可分为以下几点。

(1)表套相同,期间不同:可以通过固定表或浮动表比较同表套不同期间的数据。

(2)表套不同,期间相同:可以通过套间公式、固定表或浮动表比较同期不同表套的数据。

(3)表套不同,期间不同:可以通过套间公式、固定表比较不同任务的数据。

(2)相同任务表:表套和期间均相同的表。

2.2 报表特点

(1)由用户定义指标后得出报表,然后点击任何行或任何列,只要有数据,就能生成图形并可选择多种图形。

(2)预警分析主要用来设1置阀值,取数显示为红色。

(3)由用户自己定义选择企业/指标。

(4)报表定义可视化,主要由模板库、华表配合X M L文件实现。

(5)模板库:保存企业、区间等查询条件。

(6)华表:保存报表样式。

(7)XML:保存指标及其坐标。

3 系统实现设计

3.1 实现要点概述

3.1.1 生成分析报表表头及数据流程图(见图1)

3.1.2 报表/表达式解释规则

(1)报表内容只能由标签文字和《系统指标集》规定的符号组成。

(2)数据指标只能采用单一指标(组合指标或元指标),不能采用表达式;对与多个元指标相关的指标数据,需要通过公式定义组合指标,然后在分析报表中引入组合指标。

(3)合计求和函数@sum()与取平均值函数@average()没有包含关系而是并列关系,所以@a v e r a g e(@s u m())与@s u m(@average(.))应该是剔除解释处理。

(4)浮动表不用定义表体数据指标,而只定义表头即可;在解释表头表达式中的数据指标时,在表头区通过指标code显示指标name,而在数据区通过指标code显示指标数据值。

(5)统计分析报表时,应该分析模板的设置,得到每个数据单元格的SQL语句(其中的where条件的最基本元素包括“封面类型、指标code、公式方案”,“公式方案”是通过企业、表套、期间形成的企业任务得到的),然后批量传到后台计算,计算完成后再通过数组传回显示。

3.1.3 实现过程及主要问题点

(1)设计模板,实现保存。

(1)解释数据指标保存到分析报表指标关系表中。

(2)解释系统指标表达式保存到X M L中。

(2)提取数据,显示报表。

(1)解释表头:从XML中读出表头表达式并解释显示。

(2)解释表体。

(3)表体指标不允许用四则运算表达式,但可以用系统指标符号,如{#colflow}、{#rowflow}。

(4)把提取每个单元格的指标数据的条件(封面、企业任务、指标)传到后台处理,并以批处理的方式计算数据,放到临时表或数组中,计算完成后才一次性回显。

(5)解释表尾:从XML中读出表头表达式并解释显示,同表头解释处理。

3.2 系统实现过程的程序设计

3.2.1 解释行/列表头

(1)定义行表头数组。

(2)解释行表头表达式(从外层向里解释),得到“值、值类型、所属枚举类、父节点、是否叶子节点、表头行(X)”。

(1)根据“值、值类型”填写查询条件根据自身“值类型”把“值”填到对应的查询条件中。

(2)如果“值类型”为“计算”,则填写“计算类型”列求和或列平均。

(3)使用递归算法(求孩子节点),计算所有本节点的宽度(所有叶子节点之和),得到“表头列(Y)”。

3.2.2 行表头与列表头交叉,产生数据数组

(1)以从左到右的顺序遍历关联的行、列语法树,取得每个叶子结点的最短路径,每条路径按从上到下的顺序生成中每个结点的值的聚合,在生成行、列语法树的一维叶子数组后,产生行、列数组的卡笛尔乘积(即查询条件,以行列元素的X、Y值检索)。

(2)根据查询条件生成相应SQL,批量执行后返回结果集。

(3)将查询结果数据以一个X、Y为下标的二维数组中,分别从子向上遍历,汇总/求平均出行、列语法树上的值。

4 结语

任何企业都需要制作和管理一定数量、一定格式的报表,报表作为快速搜集并整合数据的工具已成为制定发展策略的重要依据。本文设计并实现了一种报表定义可视化,由模板库、华表配合XML文件生成数据报表的方法。实践证明,该报表工具不但操作简单,扩展性好,而且还不依赖于具体的开发平台,节省了开发成本,提高了工作效率。

参考文献

[1]侯健,曲俊华.一种基于XML的报表生成工具[J].计算机与信息技术,2007(Z1):95～96,111.

[2]职波,张征,龚婕.基于Web的Java中复杂报表的设计[J].软件技术,2001,20(4):43～45.

[3]李榕,丁岳伟,徐骁骏.基于XML的动态数据报表生成技术[J].微计算机信息,2005,21(12～3):82～84.