登录

  • 登录
  • 忘记密码?点击找回

注册

  • 获取手机验证码 60
  • 注册

找回密码

  • 获取手机验证码60
  • 找回
毕业论文网 > 开题报告 > 理工学类 > 信息与计算科学 > 正文

软件测试用例生成算法的研究开题报告

 2022-01-18 22:14:55  

全文总字数:9296字

1. 研究目的与意义及国内外研究现状

计算机的普及和发展导致系统软件层出不穷,为了使软件更好地满足人们的需求,软件的设计变得更加复杂,设计流程更加细化。但是各种各样的软件以及复杂的设计使得软件错误大量出现。美国国家标准技术研究所(nist)报告[1]指出,因为软件测试的不充分而给美国经济业带来的损失平均每年高达595亿美元,而软件测试的不充分加上软件测试的自身成本较高,可能占到整个软件开发成本的50%以上。因此测试用例生成算法问题已成为软件开发中一个很重要的问题。

根据研究结果[2],下面具体给出覆盖阵列ca的定义:测试用例通常以覆盖阵列来描述,覆盖阵列caλ(n;t,k,v)是一个定义在v原集上的nk阶矩阵,满足对于每一个nt阶子矩阵,包含v上的所有t元有序集至少一次。故可以选择测试用例,使得对于任意t(t是一个小的正整数,一般是2或者3)个参数,这zv^t个参数的所有可能取值的组合至少被一个测试用例覆盖,这种要求便对应着覆盖阵列这一组合结构。假设有k类影响系统的因素,每一类中有v种可能的配置,定义覆盖阵列caλ(n;t,k,v)为一个nk矩阵,满足对任意的nk阶子矩阵中每一个t序元至少出现λ次,其中,t称为交叉覆盖的强度。目前的研究主要集中于λ=1的情形,覆盖阵列ca' λ(n;t,k,v)便记为ca(n;t,k,v)。本课题也只讨论λ=1的情形。

剩余内容已隐藏,您需要先支付后才能查看该篇文章全部内容!

2. 研究的基本内容

2.1测试用例生成算法的目标分析

对于给定的一个系统,它包含有若干个参数,测试用例生成算法的目标是在保证测试用例集覆盖率高的情况下,尽可能地缩小用例集的规模。

2.2 测试用例生成算法的流程介绍

该算法主要包括如下解步骤:

1)将测试用例集看作是不同的点,按照一定的准则建立点与点之间的联边,从而将系统转化为图;

2)对所得到的图进行染色,并结合遗传算法进行优化求解,得到最小染色方案;

3)将图的最小染色方案转化为测试用例集生成方案。

2.2 测试用例生成算法的设计

2.2.1图模型点集合的建立:

给定一个CA(t,k,v)

2.2.2图模型边集合的建立:

定义只要全部对应位置上的取值完全相同,则两点有联边,如有两个点(k1,k2,…,kt,__,__,…,__), (v11,v21,v31,…,vt1)与(k1,k2,…,kt-1,__,…,__,kt), (v11,v21,v31,…,vt1),根据定义显然上述两个点是有联边的,而对于给定的两个点(k1,k2,…,kt,__,__,…,__), (v11,v21,v31,…,vt1)与(k1,k2,…,kt-1,__,…,__,kt), (v12,v21,v31,…,vt1)是无法联边的,因为k1位置上的取值不同。这样就建立了图模型的边集合E。

结合以上两个集合,可建立对应于CA的图模型G(V,E)。

2.2.3基于遗传算法优化的点染色算法设计:

对于已建立的图模型,就可以对G(V,E)进行点染色,如下为基于遗传算法优化的点染色算法:

1)生成初始种群:a)对于CA将其转化为图G(V,E),令该图顶点数为S,则共有S=Cktvt个顶点。对这S个顶点进行随机排序,得到一组染色顺序,该顺序将当做改个体的基因序列,并用顺序染色给出相应的染色数,取该个体的适应度为染色数倒数。

b)将步骤a)重复N此,得到一个大小为N的初始种群。

2)遗传变异:

a)对于本次遗传算法,选择用轮盘赌算法对种群个体进行选择,有如下公式可以计算出每个个体被选择的概率:

Pti=mij=1Nmj

(1)

其中mi是每个个体的适应度。并由以下公式计算出每个个体的累积概率:

fi=j=1NP(tj)

(2)

从而可以作出选择。

b)对经过选择的个体进行交叉处理,设定交叉概率为ρ,按适应度从高到低排列,对后60%的个体进行处理,生产一个交叉概率ρi,若ρi≤ρ则从个体中随机选择两个个体,随机选择两个基因位置进行交叉处理,并将这两个个体的基因进行修正;若ρiρ则表示本轮循环不进行交叉。重复b)过程N次。

c)对经过交叉的种群进行变异处理。设定变异概率为q,随机选择一个个体,产生一个变异概率qi,若qi≤q则随机选择该个体的两个基因位进行变异,并修正该个体的基因;若qiq,则不进行变异处理。并重新计算染色数。重复c)过程N次。

3)若当前生成的种群没有收敛于同一解,或并未达到设置的迭代次数T,则重复2)过程。否则停止迭代,并输出结果。

四、模型应用

基于已建立的数学模型和算法模型,通过如下实例来进行说明。

1一个4参数的系统

System

DataBase

Client

Web Server

Windows

MySQL

Chrome

IIS

LINUX

SQL Server

IE

APACHE

表1给出了一个4参数的系统,若要生成2组合的测试用例集,则根据CA定义,该系统可以表示为CA(2,4,2)。

将CA(2,4,2)转化为图模型,步骤如下:

1)由模型可知,CA的参数排列如下:

序号

参数排列

1

(System,DataBase,__,__)

2

(System,__,Client,__)

3

(System,__,__,Web Server)

4

(__,DataBase,Client,__)

5

(__,DataBase,__,Web Server)

6

(__,__,Client,Web Server)

2 CA(2,4,2)参数排列表

2)CA的取值组合如下:

序号

取值组合

1

(1,1)

2

(1,2)

3

(2,1)

4

(2,2)

3 CA(2,4,2)取值组合表

3)按照1),2)所摆出的顺序一一对应,可得到如下点集V:

点序号

结合情况

点序号

结合情况

1

(1,1,__,__)

13

(__,1,1,__)

2

(1,2,__,__)

14

(__,1,2,__)

3

(2,1,__,__)

15

(__,2,1,__)

4

(2,2,__,__)

16

(__,2,2,__)

5

(1,__,1,__)

17

(__,1,__,1)

6

(1,__,2,__)

18

(__,1,__,2)

7

(2,__,1,__)

19

(__,2,__,1)

8

(2,__,2,__)

20

(__,2,__,2)

9

(1,__,__,1)

21

(__,__,1,1)

10

(1,__,__,2)

22

(__,__,1,2)

11

(2,__,__,1)

23

(__,__,2,1)

12

(2,__,__,2)

24

(__,__,2,2)

4 CA(2,4,2)点集

4)根据定义,只要全部对应位置上的取值完全相同,则两点有联边。对以上顶点做两两判别,建立如下边集合E:

点序号

相邻点序号

点序号

相邻点序号

1

2,3,4,7,8,11,12,15,16,19,20

13

14,15,16,19,20,23,24

2

3,4,7,8,11,12,13,14,17,18

14

15,16,19,20,21,22

3

4,5,6,9,10,15,16,19,20

15

16,17,18,23,24

4

5,6,9,10,13,14,17,18

16

17,18,21,22

5

6,7,8,11,12,14,16,23,24

17

18,19,20,22,24

6

7,8,11,12,13,15,21,22

18

19,20,21,23

7

8,9,10,14,16,23,24

19

20,22,24

8

9,10,13,15,21,22

20

21,23

9

10,11,12,18,20,22,24

21

22,23,24

10

11,12,17,19,21,23

22

23,24

11

12,18,20,22,24

23

24

12

17,19,21,23

24

5CA(2,4,2)边集合

结合表4和表5,即可得到对应于CA(2,4,2)的图模型G(V,E)。

接下来展示对图G(V,E)进行基于遗传算法优化的点染色算法:

1)令N=10,则随机产生10组染色顺序,并按照算法进行顺序染色得到染色数,继而得到种群大小为10的初始种群:

编号

染色顺序

适应度

1

23,14,13,3,11,2,7,8,10,24,9,6,19,4,20,18,1,22,21,17,15,12,5,16

0.20

2

1,18,7,8,17,14,19,13,10,2,11,21,4,6,24,12,15,9,16,3,5,23,20,22

0.20

3

24,8,19,7,9,22,10,13,23,16,21,6,17,2,3,1,14,15,20,18,11,4,5,12

0.17

4

17,1,3,2,7,6,24,19,22,5,12,23,13,15,21,11,14,9,16,8,4,18,20,10

0.17

5

2,3,9,24,18,21,8,16,20,5,14,13,22,15,17,1,12,23,4,6,19,10,11,7

0.14

6

15,14,21,9,2,3,12,19,18,8,16,1,24,7,17,6,22,10,5,11,20,4,13,23

0.17

7

16,13,9,23,7,4,21,19,5,20,3,18,24,2,1,11,12,8,10,15,14,22,6,17

0.20

8

12,11,21,16,6,2,14,4,19,18,20,3,10,24,5,22,8,9,1,17,15,13,23,7

0.17

9

15,12,23,1,10,18,5,8,7,16,13,4,2,9,3,11,17,20,24,22,6,19,14,21

0.17

10

1,23,11,6,15,17,10,13,24,12,8,9,4,19,18,7,22,5,3,21,20,14,16,2

0.17

6 初始种群

2)令t=0,运用按照算法模型中的轮盘赌算法选择出应该遗传下来的个体,为{1,2,6,7,8}。

3)根据算法中定义的交叉方法,定义交叉概率ρ=0.8,并将个体按适应度从高到低排序,把操作区间限定在后6个个体中,共进行10次交叉操作,得到10次交叉概率如下:

P1=(0.201819 0.848933 0.5719780.959807 0.615314 0.032319 0.832728 0.2067320.650472 0.560228)

从而可以判断共进行了7次交叉操作。得到如下结果:

编号

染色顺序

适应度

1

12,11,21,16,6,2,14,4,19,18,20,5,10,24,3,22,8,9,1,17,15,13,23,7

0.20

2

16,13,9,23,7,4,21,19,5,20,3,18,24,2,1,11,12,8,10,15,14,22,6,17

0.20

3

16,13,9,23,7,4,21,19,5,20,3,18,24,2,1,11,12,8,10,15,14,22,6,17

0.20

4

12,11,21,16,6,2,14,4,19,18,20,5,10,24,3,22,8,9,1,17,15,13,23,7

0.20

5

15,12,23,1,10,18,3,8,7,16,13,4,2,9,5,11,17,20,24,22,6,19,14,21

0.17

6

15,14,21,9,2,3,12,19,7,16,8,1,24,18,17,6,22,10,5,11,20,4,13,23

0.17

7

15,12,23,1,10,18,3,8,7,16,13,4,2,9,5,11,17,20,24,22,6,19,14,21

0.17

8

15,12,23,1,10,18,3,8,7,16,13,4,2,9,5,11,17,20,24,22,6,19,14,21

0.17

9

12,11,21,16,6,2,14,4,19,18,20,5,10,24,3,22,8,9,1,17,15,13,23,7

0.20

10

15,14,21,9,2,3,12,19,7,16,8,1,24,18,17,6,22,10,5,11,20,4,13,23

0.17

7 进行一次交叉后的种群

可见适应度为0.14的个体已不存在。

4)对已经进行过交叉处理的种群进行变异,定义变异概率q=0.1,共进行10次变异操作,得到10个变异概率如下:

P2=(0.009827 0.723685 0.3620410.384350 0.568224

0.464736 0.259590 0.905240 0.755852 0.290506)

从而可以判断共进行了1次变异操作。结果如下:

编号

染色顺序

适应度

1

12,11,21,16,6,2,14,4,19,18,20,5,10,24,3,22,8,9,1,17,15,13,23,7

0.20

2

16,13,9,23,7,4,21,19,5,20,3,18,24,2,1,11,12,8,10,15,14,22,6,17

0.20

3

16,13,9,23,7,4,21,19,5,20,3,18,24,2,1,11,12,8,10,15,14,22,6,17

0.20

4

12,11,21,16,6,2,14,4,19,18,20,5,10,24,3,22,8,9,1,17,15,13,23,7

0.20

5

15,14,23,1,10,18,3,8,7,16,13,4,2,9,5,11,17,20,24,22,6,19,12,21

0.20

6

15,14,21,9,2,3,12,19,7,16,8,1,24,18,17,6,22,10,5,11,20,4,13,23

0.17

7

15,12,23,1,10,18,3,8,7,16,13,4,2,9,5,11,17,20,24,22,6,19,14,21

0.17

8

15,12,23,1,10,18,3,8,7,16,13,4,2,9,5,11,17,20,24,22,6,19,14,21

0.17

9

12,11,21,16,6,2,14,4,19,18,20,5,10,24,3,22,8,9,1,17,15,13,23,7

0.20

10

15,14,21,9,2,3,12,19,7,16,8,1,24,18,17,6,22,10,5,11,20,4,13,23

0.17

7 进行一次交叉后的种群

可以看到第5个个体发生了变异,且适应度更高了。

将以上步骤迭代多次,直到个体适应度收敛于同一值,或迭代T次结束,即可得到染色数最少的染色方案,从而得到测试用例生成方案。

以上即为图模型的建立以及算法在实际案例中的使用,可以看到该方法具有实用性,可以在保证测试用例集覆盖率高的情况下,生成小规模的测试用例集。

3. 实施方案、进度安排及预期效果

实施方案:根据测试用例集的定义及原理,通过研究测试用例集的结构,发现测试用例集的组成结构与图论有着相似性。本课题希望通过图论的知识,建立点染色模型,运用图论方法生成测试用例集,并通过对点染色进行操作,以此间接操作测试用例集,通过求解最小染色数来求解最小规模的测试用例集。

进度安排:3月初到3月中旬进行模型的建立,3月下旬进行代码的编写,4月初完成论文初稿,4月中旬开始论文修改。

预期结果:内容上因为测试用例集的组成结构与图论有着相似性,因此认为依据点染色模型的测试用例生成算法是可行的。若代码编写合理,对数据处理适当,最终可以得到一个不错的结果。时间上可以顺利按照进度安排进行,并在论文截止日期前完成论文定稿。

剩余内容已隐藏,您需要先支付后才能查看该篇文章全部内容!

4. 参考文献

[1]tassey ,gregory. the economic impacts of inadequate infrastructure for softwaretesting. national institute of standards and technology, rti project, citeseer,2002, 7007

[2]wang yu.relevant constructions of covering arrays , beijing jiaotong university,2012

[3] soumenmaity, amiya nayak, marzia zaman, nita bansal, alka srivastava. an improvedtest generation algorithm for pairwise testing[r]. ieee international symposium onsoftware reliability engineering. 10.1109/issre.2005.23

剩余内容已隐藏,您需要先支付 5元 才能查看该篇文章全部内容!立即支付

微信号:bysjorg

Copyright © 2010-2022 毕业论文网 站点地图