软件测试用例生成算法的研究开题报告
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参数的系统 | ||||||||||||
|
表1给出了一个4参数的系统，若要生成2组合的测试用例集，则根据CA定义，该系统可以表示为CA(2,4,2)。
将CA(2,4,2)转化为图模型，步骤如下：
1）由模型可知，CA的参数排列如下：
| ||||||||||||||
| 表2 CA(2,4,2)参数排列表 |
2）CA的取值组合如下：
| ||||||||||
| 表3 CA(2,4,2)取值组合表 |
3）按照1），2）所摆出的顺序一一对应，可得到如下点集V：
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
| 表4 CA(2,4,2)点集 |
4）根据定义，只要全部对应位置上的取值完全相同，则两点有联边。对以上顶点做两两判别，建立如下边集合E：
|
表5CA(2,4,2)边集合
结合表4和表5，即可得到对应于CA(2,4,2)的图模型G(V,E)。
接下来展示对图G(V,E)进行基于遗传算法优化的点染色算法：
1）令N=10，则随机产生10组染色顺序，并按照算法进行顺序染色得到染色数，继而得到种群大小为10的初始种群：
|
表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次交叉操作。得到如下结果：
|
表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次变异操作。结果如下：
|
表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
您可能感兴趣的文章
- UI 和 UE 设计技术及其在 HTML5 网站开发中的地位的研究外文翻译资料
- .NET MVC框架在开发农业资源清单系统中的适应性外文翻译资料
- 使用Java平台针对数据库桥接层的Spring框架可靠性调查外文翻译资料
- 基于MVC架构的数据库和Web应用程序外文翻译资料
- 利用微服务SpringBoot 设计和开发公众投诉系统的后端应用。外文翻译资料
- 基于SSM框架的校园自行车租赁管理系统统计外文翻译资料
- 基于Android的校园交友社交应用的设计与开发外文翻译资料
- 基于Android的在线社交系统服务端的设计与实现外文翻译资料
- 基于Spring-boot微服务框架的学生成绩分析系统的设计与实现外文翻译资料
- 用于生成计算材料科学文献中使用的方法和参数的数据库的自动化工具外文翻译资料
