3.3.3 爬山法实验
1.爬山法性能分析
在本实验中,通过使用路径变量性质确定初始值的爬山法与变量个数和表达式个数之间的关系来分别验证初始值选取策略和爬山过程的效果。由此,我们进行了3种方法的对比,这3种方法分别为随机初始值和矛盾后不爬山(Random Initial value and No Hill Climbing,RI&NHC)、随机初始值和矛盾后爬山(Random Initial value and Hill Climbing,RI&HC)、通过使用路径变量性质确定初始值和矛盾后爬山(BB-HC)。因为使用这3种方法测试用例生成时间差别较大,我们对代表测试用例生成时间的坐标轴进行了指数化处理。
(1)与变量个数的关系
通过测试变量个数与3种测试用例生成方法的关系来进行对比。为此,进行了如下的实验设置:将被测程序设置为50个输入变量x 1,x 2,…,x n,其中n从1顺次递增到50。采用语句覆盖,在每个被测程序中设置50个if语句(相当于50个路径约束),而且只有一条待覆盖路径,即完全由真分支(TTT…TT)构成的路径,从而分支条件与分支谓词完全一致。每个if语句都是n个变量的线性组合,表现为如下形式:
其中,a 1,a 2,…,an是或正或负的随机数,rel_op∈{＞,≥,＜,≤,=,≠},const[c](c∈[1,50])是一个[0,1 000]内随机常数的数组。需要对随机数ai和const[c]进行验证确保路径可达,并且为了考察3种方法处理等式的能力,在每个被测程序中要保证至少有一个“=”。这样的设置建立起了这样的一种变量关系:它们之间是最紧密的线性关系,而且它们都是待覆盖路径的相关变量。对于n从1到50之间的每个值所对应的每个被测程序都使用3种方法进行了50次实验,对每次实验的测试用例生成时间都进行了记录,并取平均值进行比较。实验结果如图3-18所示。
可以看出,BB-HC的平均生成时间要远小于另外两种方法,而初始赋值和矛盾后赋值都随机的方法RI&NHC用掉了最多的时间。BB-HC的平均生成时间随着变量个数的增加呈匀变速增长。对拟合曲线求导可以得出y=1.06x-8.682,据此可以大致推断:当n小于8时,测试用例生成时间大致相当;而当n大于8时,测试用例生成时间开始增长。
图3-18 3种方法与变量个数的关系对比
(2)与表达式个数的关系
通过测试表达式个数与3种测试用例生成方法的关系来进行对比。为此,进行了如下的实验设置:将被测程序设置为50个输入变量x 1,x 2,…,x 50,采用语句覆盖,在每个被测程序中设置u(u∈[1,50])个if语句(相当于u个路径约束),而且只有一条待覆盖路径,即完全由真分支构成的路径,从而分支条件与分支谓词完全一致。每个if语句都是n个变量的线性组合,表现为如下形式:
其中,a 1,a 2,…,a 50是或正或负的随机数,rel_op∈{＞,≥,＜,≤,=,≠},const[u]是一个[0,1 000]内随机常数的数组。需要对随机数a v(v=1,2,…,50)和const[u]进行验证确保路径可达,并且为了考察3种方法处理等式的能力,在每个被测程序中要保证至少有一个“=”。对于u从1到50之间的每个值所对应的每个被测程序都使用3种方法进行了50次实验,对每次实验的测试用例生成时间都进行了记录,并取平均值进行比较。实验结果如图3-19所示。
图3-19 3种方法与表达式个数的关系对比
可以看出,BB-HC的平均生成时间要远小于另外两种方法,而初始赋值和矛盾后赋值都随机的方法RI&NHC用掉了最多的时间。对曲线进行拟合可以得出,使用BB-HC时,测试用例生成时间和表达式个数呈线性关系,即当表达式个数增加的时候,BB-HC的平均生成时间也会随之线性增长。
2.爬山法处理等式对比实验(https://www.daowen.com)
(1)实验设计
作为主要的求解策略,将爬山法应用于分支限界中就是为了解决由于等式引起的求解失败问题。为了检验爬山法对于等式的处理能力,保持其他为最优策略,本实验将测试分支限界处理表达式能力实验201个分支的例子中不等式依次改为1个、2个、3个、4个、5个等式,并观察其效果。只选取带有等式的路径进行实验,选取语句覆盖,每种情况实验20次,取平均值作为统计。
(2)实验环境
①CPU为Intel(R)Pentium(R)CPU U5600@1.33GHz。
②主板为联想3249A69(英特尔QM57)。
③内存为4 GB(2.92 GB可用)。
④显卡为Intel(R)HD Graphics(Pentium)。
⑤硬盘为希捷ST9250315AS。
⑥操作系统为Windows 7家庭普通版。
(3)实验数据
表3-10为爬山法处理等式的实验结果。
表3-10 爬山法处理等式实验结果
(4)实验总结
从表3-10可以看出,当等式个数较少时,对于分支限界影响不大,回溯次数和生成时间接近无等式时的情况。当等式个数从3开始递增的时候,回溯次数和生成时间都增长得很快。通过对于整个执行过程的跟踪分析,对于带有等式的被测程序,可以做出以下两点改进。
①等式的优先级要高于不等式的优先级,最主要的原因就是等式的约束更加严格、更难满足,应该优先处理等式,所以需要单独处理约束中的等式提取。
②现在的爬山法处理策略过分依赖区间运算的结果,其实可以将单独提取的等式看作关于输入变量的方程组,借助于线性代数中对于线性方程组是否有解的判断法(如系数矩阵的秩)来辅助判断赋值选取的正确与否。
