4.2.5 实验分析
为了观察BFS-BB-IIA的效果,我们在CTS框架内做了大量实验。这其中包括与著名的弧一致性检查算法AC-3的对比实验;考虑到变量个数和表达式个数是影响测试用例生成的重要指标,因此我们通过实验检查VAD部分对不同变量个数和不同表达式个数的实验效果;我们将BFS-BB-IIA与常见的测试工具C++test以及著名的约束求解器Choco进行了对比实验。
1.弧一致性检查评估
这一部分是IIA与AC-3之间的对比实验。由于弧一致性算法经常与搜索算法结合使用,因此我们在BFS-BB框架内进行实验。也就是说,实验所对比的是BFS-BB-IIA与BFS-BB和AC-3的组合。实验环境为32位MS Windows 7操作系统,Pentium 4处理器,主频3.00 GHz,内存4 GB。被测程序是N皇后问题,其中N的范围为4~11。这里需要注意一个相关问题,就是按照什么顺序来对变量的区间进行一致性检查。已经有研究表明,这个排序的启发规则会对AC-3的性能产生显著影响,所以为了公平起见,我们假定实验按照数字顺序来进行。
对于测试用例生成来说,一个解已经足够了,所以我们所比较的是当得到第一个解时,AC-3和IIA约束检查的次数和回溯的次数。表4-9所示是实验结果,可以看出,IIA在约束检查的次数和回溯的次数这两个方面都优于AC-3,这意味着当第一个解被求出来的时候,BFS-BB-IIA相比于BFS-BB和AC-3的组合在搜索树上访问了更少的节点。
表4-9 AC-3和IIA对比的结果
2.测试用例生成性能评估
(1)测试不同的变量个数
变量个数是影响测试用例生成方法性能的一个重要指标。在这一部分中,主要关注不同的变量个数与两种算法(有和没有VAD)的性能之间的关系。将被测程序设置为100个输入变量x 1,x 2,…,x n,其中n从1顺次递增到100。采用语句覆盖,在每个被测程序中设置100个if语句(相当于每次区间运算要计算100个路径约束),而且只有一条待覆盖路径,即完全由真分支构成的路径,从而分支条件与分支谓词完全一致。每个if表达式都是如下形式:
其中,a 1,a 2,…,a n是或正或负的随机数,rel_op∈{＞,≥,＜,≤,=,≠},const[c](c∈[1,100])是一个随机常数的数组。需要对随机数ai(1≤i≤n)和const[c]进行验证确保路径可达。这样的设置建立起了n个变量之间最紧密的线性关系。对于n从1到100之间的每个值所对应的每个被测程序都进行了100次实验,对每次实验所耗费的测试用例生成时间都进行了记录。实验环境为32位MS Windows 7操作系统,Intel Core处理器,主频2.4 GHz,内存2 GB。对比结果如图4-15所示,当变量个数不是很大时,两种方法的生成时间很接近,所以使用对数坐标系从而更好地对两种方法进行区分。
图4-15 当变量个数增加时迭代方法与非迭代方法的对比实验结果
图4-15说明迭代方法的生成时间要远小于非迭代方法的生成时间。对于迭代方法来说,测试用例生成时间可以被拟合成变量个数的多项式形式(如图4-16所示),在95%置信区间内其p值远小于0.05。另外,测试用例生成时间随着变量个数的增加以均匀的加速度增加。对拟合函数进行求导,可以得到y=904.4x-12 190,也就是说随着变量个数的增加,测试用例生成时间以904.4x-12 190的加速度增加。我们可以得出大概的结论:在其他设置保持不变的情况下,当n从1增加到13时,使用VAD的方法其生成时间是非常接近的,而当n大于14时,测试时间开始明显增加。
图4-16 当变量个数增加时迭代方法的拟合结果
(2)测试不同的表达式个数
表达式个数是影响测试用例生成方法性能的一个重要指标。在这一部分中,主要关注不同的表达式个数与两种算法(有或没有VAD)的性能之间的关系。将被测程序设置为100个输入变量x 1,x 2,…,x 100。采用语句覆盖,在每个被测程序中设置u(u∈[1,100])个if语句(相当于每次区间运算要计算u个路径约束),而且只有一条待覆盖路径,即完全由真分支构成的路径,从而分支条件与分支谓词完全一致。每个if表达式都是如下形式:
其中,a 1,a 2,…,a 100是或正或负的随机数,rel_op∈{＞,≥,＜,≤,=,≠},const[u]是一个随机常数的数组。需要对随机数a v(v=1,2,…,100)和const[u]进行验证确保路径可达。这样的设置建立起了100个变量之间最紧密的线性关系。对于u从1到100之间的每个值所对应的每个被测程序都进行了100次实验,对每次实验所耗费测试用例生成时间都进行了记录。实验环境为32位MS Windows 7操作系统,Pentium 4处理器,主频3.00 GHz,内存4 GB。对比结果如图4-17所示,当表达式个数不是很大时,两种方法的生成时间很接近,所以使用对数坐标系从而更好地对两种方法进行区分。图4-18说明迭代方法的生成时间要远小于非迭代方法的生成时间。对于迭代方法来说,测试用例生成时间可以被拟合成变量个数的线性表示,在95%置信区间内其p值远小于0.05。测试用例生成时间随着表达式个数的增加均匀增长。
图4-17 当表达式个数增加时迭代方法与非迭代方法对比实验结果
图4-18 当表达式个数增加时迭代方法的拟合结果(https://www.daowen.com)
3.与其他测试用例生成方法的比较
(1)与BFS-BB比较
采用MC/DC覆盖,BFS-BB-IIA测试aa200c使用了将近66 min的时间,是BFS-BB用时的2/3,且其中34%的不可达路径被检测出来。在这一部分,我们使用来自http://www.moshier.net/的两个工程来比较BFS-BB-IIA和BFS-BB。实验环境为32位Ubuntu 12.04操作系统,Pentium 4处理器,主频2.8 GHz,内存2 GB。待覆盖路径来自CTS,这其中可能包含不可达路径。对比采用3种覆盖准则:语句、分支、MC/DC。对于每个待测项都进行了100次实验,对比的参数包括检测出的不可达路径数、平均测试用例生成时间和平均覆盖率。不可达路径上的元素不纳入覆盖率统计。对比结果如表4-10所示。
表4-10 BFS-BB-IIA与BFS-BB的对比实验结果
①不可达路径检测。如第6列加粗所示,大概半数的情况都包含不可达路径,BFSBB无法检测不可达路径,但是BFS-BB-IIA可以,这是一个非常有效的功能,因为省去了后续生成测试用例的步骤。
②生成时间。如第7列加粗所示,在所测试的18例中,BFS-BB-IIA对于其中11例消耗了比BFS-BB更少的时间。有7例BFS-BB-IIA消耗的时间更多,这是因为IIA执行了两轮,但是第一轮就完成了对所有变量的区间削减,而第二轮只是起到验证的作用。在这种情况下,非迭代方法显然更快(省掉了第二轮的时间)。
③覆盖率。如第9列加粗所示,在所测试的18例中,BFS-BB-IIA对于其中5例得到了比BFS-BB更高的覆盖率。两种方法对于另外13例取得了相同的覆盖率,包括9个100%。在BFS-BB-II没有取得100%的例子中,大部分是采用了MC/DC覆盖准则,它包含了语句覆盖和分支覆盖,相对来说更加严格也更难满足。
(2)与C++test比较
这一部分是BFS-BB-IIA和C++test的对比实验,其中C++test是以Visual Studio 2008的插件形式存在的。实验环境为32位MS Windows 7操作系统,Pentium 4处理器,主频3.00 GHz,内存4 GB。对比实验采用语句覆盖。对每个被测程序都进行了100次实验,通过平均生成时间和平均覆盖率进行比较。被测程序的细节信息如表4-11所示。对比结果如表4-12所示,我们基于被测程序的特点从3个方面进行讨论,其中对BFS-BB-IIA表现更好的地方进行了加粗显示。
表4-11 用于与C++test对比的程序
①表达式个数。前4个程序中分别有50个、100个、150个和200个数学表达式,但是由于变量个数不同,所以实验结果并不遵守之前的实验结论,BFS-BB-IIA的生成时间也并不遵守拟合结果。当表达式个数在100以内时,C++test花费的时间更少,但是其覆盖率也很低。从覆盖率的角度来说,BFS-BB-IIA的性能更好。而随着表达式个数的增加,求解约束的难度也随之增加,当表达式超过150个时,C++test已经无法求解。而BFS-BB-IIA能够求解表中的数百个表达式并达到较高的覆盖率,当然求解时间也会随之增加。
②变量类型。可以从第2列和第4列看出,对于包含基本类型的程序,BFS-BB-IIA的表现更好(除了前两个程序),都获得了更少的生成时间和更高的覆盖率。对于大多数情况,C++test的生成时间都数倍于BFS-BB-IIA。C++test无法为要求为NULL的输入生成测试用例(如最后一个被测程序),而随机生成的测试用例会让程序的执行出错,也就意味着测试用例生成失败。BFS-BB-IIA能够为它生成测试用例,但是覆盖率也没有到达100%。
③循环。对于11个带有循环的程序,BFS-BB-IIA都在达到100%覆盖率的基础上花费了更少的时间。但是这11个程序都来自CTS,我们应该尝试更多来自实际工程的项目来测试其能力。
表4-12 BFS-BB-IIA与C++test的对比结果
(3)与Choco比较
这一部分是IIA与一个开源的约束求解器Choco之间的对比,我们在BFS-BB框架内进行实验。也就是说,实验所对比的是BFS-BB-IIA与BFS-BB和Choco的组合。被测程序来自工程de118i-2(http://www.moshier.net/)和工程people(来自佛罗里达州立大学C源代码库,http://people.sc.fsu.edu/~jburkardt/c_src/c_src.html)。实验环境为32位Ubuntu 12.04操作系统,Pentium 4处理器,主频3.00 GHz,内存4 GB。待覆盖路径由CTS提供,其中可能包含不可达路径。比较采用3种覆盖准则:语句、分支、MC/DC。对每个被测程序都用两种方法测试了100次,记录检测出的不可达路径数、平均生成时间和平均覆盖率并进行比较。不可达路径上的元素不纳入覆盖率的计算。比较的具体细节如表4-13所示,我们从3个方面进行讨论。
①不可达路径检测。如第6列加粗所示,大概半数的情况都包含不可达路径,Choco无法检测不可达路径,但是BFS-BB-IIA可以,这是一个非常有效的功能,因为省去了后续生成测试用例的步骤。
②生成时间。对于所有情况,Choco所使用的生成时间都数倍于BFS-BB-IIA,如第7列所示,可以看出有些甚至高达数十倍。从测试时间这个角度来说,BFS-BB-IIA相比于Choco具有非常明显的优势。
③覆盖率。在所有的情况下,BFS-BB-IIA的覆盖率都高于Choco。Choco没有一种情况达到100%的覆盖率。而BFS-BB-IIA除了5个案例外都达到了100%,其中4个案例采用了MC/DC。MC/DC是相对严格的,我们将进一步研究。
表4-13 BFS-BB-IIA与Choco对比实验结果
