4.1.5 实验分析
为了观察BFS-BB-HB的效果,我们在CTS框架内做了大量实验。考虑到闭包是本章所提出的影响测试用例生成的重要指标,因此我们通过实验检查不同的闭包个数对生成时间和回溯次数的影响;使用BFS-BB-HB测试了一个实际工程项目;对使用FC-CBJ的方法(BFS-BB-HB)与使用FC(BFS-BB)的方法进行了对比,测试程序来自一些常见的CSP问题;使用N皇后问题,将BFS-BB-HB与常见的测试工具C++test进行了对比实验。
1.测试不同的闭包个数
闭包是本章所提出的影响测试用例生成的重要指标。使用BFS-BB-HB测试不同的被测程序,将被测程序设置为10个输入变量x 1,x 2,…,x 10。采用语句覆盖,每个被测程序中包含n(n∈[1,10])个if语句(相当于每次区间运算要计算n个路径约束),而且只有一条待覆盖路径,即完全由真分支构成的路径,从而分支条件与分支谓词完全一致。每个表达式都包含所有10个变量,而它们可能处于不同的闭包中。我们尽量让每个闭包中包含相同个数的变量:当有1、2、5个闭包时,每个闭包中都包含相同个数的变量,分别是10、5、2;而当有3个闭包时,每个闭包中的变量个数分别是3、3、4;当有4个闭包时,每个闭包中的变量个数分别是2、2、3、3。以有2个闭包为例,每个if表达式都是如下形式:
其中,a n 1,a n 2,…,a n 10(n=1,2,…,10)是或正或负的随机数,rel_op∈{＞,≥,＜,≤,=,≠},const[n][2]是一个随机常数的数组。需要对随机数ani(i=1,2,…,10)、const[n][1]和const[n][2]进行验证确保路径可达。这样的设置建立起了同一闭包内变量之间最紧密的线性关系。对于n从1到10之间的每个值所对应的每个被测程序都进行了100次实验,对每次实验所耗费测试用例生成时间都进行了记录。实验环境为32位MS Windows 7操作系统,Pentium 4处理器,主频3.8 GHz,内存4 GB。对比结果如图4-8和图4-9所示。
从图4-8(a)可以看出,当闭包个数固定时,平均测试时间随着表达式个数的增加而增长,尤其是当被测程序中包含6~10个表达式时就更明显。其原因是随着表达式个数的增加,约束的复杂性也随之增加,而当约束较少时基本都是无回溯的搜索(所以约束少时效果不明显)。图4-8(b)说明对于相同个数的表达式,平均测试时间随着闭包个数的增加而缩短。因为更多的闭包意味着每个约束内的变量个数更少,从而降低了搜索的复杂度。上述结论对于回溯次数与闭包个数的关系也同样成立,如图4-9所示。
图4-8 平均测试时间与闭包个数的关系
2.测试工程项目
图4-9 平均回溯次数与闭包个数的关系
在这一部分,我们使用BFS-BB-HB来测试实际工程项目。实验采用语句覆盖,实验环境为32位MS Windows 7操作系统,Intel Pentium(R)G640处理器,主频2.80 GHz,内存2 GB。被测工程为aa200c,而选择的被测程序都包含多变的数据结构和变量类型。测试结果如表4-3所示。区间运算之前介绍过,我们用它来衡量BFS-BB-HB中前向检查的性能。可以从这个表中得出两点结论。第一,当被测程序中没有指针时,BFS-BBHB表现更好。我们应该投入更多精力来处理指针类型。第二,由于表达式的个数会影响搜索的效率[4],因此相同的约束检查个数也可能导致不同的时间开销。总体来说,BFS-BB-HB在可接受的时间内表现良好,但是仍需要优化。
表4-3 使用BFS-BB-HB测试工程aa200c的结果
续表
3.BFS-BB-HB和BFS-BB的比较
在这一部分进行BFS-BB-HB和BFS-BB的对比实验。实验环境为32位MS Windows 7操作系统,Pentium 4处理器,主频3.8 GHz,内存4 GB。
(1)测试CSP问题(https://www.daowen.com)
选择来自http://www.csplib.org/Problems/的一些CSP问题作为被测程序。搜索树向上回一步就代表着执行了一次回溯操作。选择的第一个CSP问题是N皇后问题,对每个被测程序(n=4,5,…,9)都实验了100次,记录平均回溯次数和平均时间开销并进行比较。
测试结果如表4-4所示,这个结果与N皇后问题解的分布(表4-5)是一致的,可以看出6皇后解的个数比5皇后少。由于1皇后太简单了,2皇后和3皇后问题无解,因此我们在实验中,n从4开始。对于所有的被测程序,BFS-BB-HB都比BFS-BB效果好,如表4-4中加粗所示。
表4-4 使用BFS-BB-HB和BFS-BB测试N皇后问题对比实验结果
表4-5 N从1到9时N皇后问题解的分布
另外选择的两个CSP问题是4阶幻方和魔幻六边形。对每个被测程序都实验了100次,记录平均回溯次数、平均约束检查次数和平均时间开销并进行比较。表4-6展示了实验结果,可以看出BFS-BB-HB的表现全部优于BFS-BB:从平均回溯次数来说,BFSBB-HB分别是BFS-BB的12%和42%,如第4列所示;从平均约束检查次数来说,BFSBB-HB分别是BFS-BB的24%和48%,如第7列所示;从平时间开销来说,BFS-BB-HB分别是BFS-BB的21%和47%,如第10列所示。
表4-6 测试两个CSP问题的结果
总体来说,BFS-BB-HB对选中的CSP问题表现良好,尤其是从提高回溯效率的角度来说。今后我们会测试更多的CSP问题来验证算法的效率并进行改进。
(2)测试CTS的一个benchmark
实验环境为32位Ubuntu 12.04操作系统,Pentium 4系统,主频2.8 GHz,内存2 GB。被测程序是branch_bound.c,它是CTS组的一个benchmark,代码行数为402,有29个输入变量,其程序结构较为复杂,试图包含可能出现在工程中的程序结构。采用语句覆盖,有65条待测路径。对每条路径都进行了100次测试,记录平均时间和平均回溯次数。两种方法对于其中的45条路径都没有产生回溯,这里我们不对其进行讨论。而对于有回溯的20条路径,对比结果如表4-7所示,可以看出回溯次数总体上减少了53%,测试时间总体减少了38%,BFS-BB-HB极大地提高了搜索效率。
表4-7 测试CTS的一个benchmark的结果
4.BFS-BB-HB和C++test的比较
这一部分进行BFS-BB-HB和C++test的对比实验,其中C++test是以Visual Studio 2008的插件形式存在的。实验环境为32位MS Windows 7操作系统,Pentium 4处理器,主频3.8 GHz,内存4 GB。对比实验采用语句覆盖。被测程序为N皇后问题,对每个被测程序(n=4,5,…,9)都实验了100次,记录平均回溯次数和平均时间开销并进行比较。对比结果如表4-8所示,其中对BFS-BB-HB表现更好的地方以加粗显示。第一,由于BFS-BB-HB强大的求解能力,其对所有的被测程序都达到了100%的语句覆盖率,而C++test无法求解N皇后问题的所有约束,导致覆盖率远小于100%。第二,对于所有例子,C++test的时间开销都数倍于BFS-BB-HB。当问题的解较少(表4-5)时,BFS-BB-HB的优势更明显。
表4-8 使用BFS-BB-HB和C++test测试N皇后问题对比结果
