3.1.6 不相关变量移除
1.算法介绍
如前所述,X={x 1,x 2,…,x n}是被测程序PUT的输入变量集合。被搜索的状态空间应该考虑到X中每一个x i(i=1,2,…,n)的可能取值。但是并非每个x i都会影响到PUT中每条路径的可达性。仍以图3-2中的被测程序test1为例,如果采用分支覆盖,则有4条待覆盖路径。但是输入变量x 3只与Path2:0→1→3→4→8→9→10、Path3:0→1→3→5→6→7→8→9→10和Path4:0→1→3→5→7→8→9→10相关,而与Path1:0→1→2→9→10无关。因此,在为Path1生成测试用例时,对于x 3所做的搜索是无用的,因为它的取值并不会影响Path1的可达性。所以从状态空间中移除对于路径不相关的输入变量,而只考虑相关变量,将会提高搜索过程的效率。相关变量和不相关变量的定义如下。
图3-6 变量级别确定算法流程图
定义3-5 路径p的相关变量(relevant variable)是能够影响p是否可达的输入变量。具体来说,对于所有输入变量的集合{x i|x i∈X,i=1,2,…,n}中的每一个变量,存在着一组相应的赋值{V i|V i∈Di,i=1,2,…,n},这组赋值使得p不可达。但是若对应于某一个变量的赋值改变了,例如,x g的值从V g变成了V′g,输入{V 1,V 2,…,V′g,…,V n}令p可达,则x g是路径p的一个相关变量。
定义3-6 路径p的不相关变量(irrelevant variable)是不能影响p是否可达的输入变量。具体来说,对于所有使得路径p不可达的输入变量值的集合{V i|V i∈Di,i=1,2,…,n},若对应于某一个变量的赋值改变了,例如,x g的值从V g变成了V′g,输入{V 1,V 2,…,V′g,…,V n}仍然令p不可达,则x g是路径p的一个不相关变量。
之所以会出现不相关变量,正是由于区间抽象域无法表示出变量之间的关系。通过静态分析技术可以判断变量对于路径的相关性并进行不相关变量移除(Irrelevant Variable Removal,IVR),从而缩小算法的搜索空间。
通常来说,对于某一条路径,每个变量是否与路径相关或不相关并不能完全确定下来,这是由被测程序的结构复杂与否来决定的。但是我们仍然可以通过静态分析技术对变量与路径的相关性进行保守估计。下面的分析考虑到被测程序中最常见的情况,即每个谓词条件是输入变量的线性表达式。假如路径上有k个分支,为了确定一条路径的相关变量,则需要对于每一个分支(nqa,nqa+1)(a∈[1,k])进行访问,即需要判断是否每个变量出现在每个分支上。所以我们给出下面的定义和算法。结合算法BFS-BB的复杂性和变量个数的关系,我们给出命题3-1来计算IVR的效果。
定义3-7 分支条件Br(nqa,nqa+1)是分支(nqa,nqa+1)(a∈[1,k])上的约束,它可以表示成如下形式:(https://www.daowen.com)
其中,R是关系运算符,aj(j∈[1,n])和c都是常数。
命题3-1 对于某条路径来说,采用IVR相比于不采用IVR,可以使算法3-1消耗更少的区间运算次数,从而降低算法的复杂度。
证明 算法3-6(后面会详细介绍)是在其他变量保持不变的情况下,对同一个变量连续进行赋值的过程,每次赋值都会消耗一次区间运算,最坏的情况就是用掉了所有m次机会。由此我们可以得到算法的时间复杂度是O(mn)。令X rel代表路径p的相关变量集合,X irrel代表路径的不相关变量集合,则每当X rel里多一个元素,算法所耗费的区间运算将会以指数级增长。如果所有的不相关变量都从搜索空间中移除,则算法的时间复杂度将会降低m|X irrel|。|X irrel|是不相关变量集合里的元素个数。以上是不回溯情况下的结果,而在线性约束的情况下,BFS-BB所执行的多是不回溯的搜索,所以IVR对于BFS-BB的效率提升是很明显的。
2.实例分析
本实例用来说明不相关变量移除的过程。对图3-2所示程序采用分支覆盖,有4条待覆盖路径,分别为Path1:0→1→2→9→10、Path2:0→1→3→4→8→9→10、Path3:0→1→3→5→6→7→8→9→10和Path4:0→1→3→5→7→8→9→10。我们对所有路径进行IVR处理,可以得到表3-2所示的处理过程,对于检测出不相关变量的位置以加粗表示。
表3-2 对图3-2进行IVR处理过程
