软件测试用例生成算法的研究开题报告
2022-01-18 10:01
全文总字数：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
