3.1.1　问题定义

许多测试用例生成问题都涉及待测程序P的控制流图(Control Flow Graph,CFG)。程序P的控制流图是一个有向图G=(N,E,i,o),其中N是语句节点的集合,E是有向边的集合,i和o分别是唯一的入口和出口节点。每个节点n∈N代表程序中的一条语句,而每条边e=(nr,nt)∈E则代表从节点n r到节点n t的控制转移。对应于判断语句(如if或while)的节点为分支节点,分支节点的出边叫作分支。我们所说的路径就是CFG中的一个节点序列W=(n 1,n 2,…,nq),其中对于1≤r＜q,有(nr,n r+1)∈E。

如果存在一组输入,当执行这组输入的时候,所经过的路径为W,则称路径W可达,否则称路径W不可达。这样,面向路径的测试用例生成问题可以被定义成一个约束满足问题:X是输入变量的集合{x 1,x 2,…,x n},D={D 1,D 2,…,D n}是区间集(即Domain,由区间interval构成,为了便于说明将区间集简称为区间)的集合,其中Di∈D(i=1,2,…,n)是可能赋给x i的所有值的集合。该问题的一个解是每个变量都有在其区间内的一个值,表示成V={V 1,V 2,…,V n},V i∈Di,它使得待覆盖路径可达。路径的可达性在静态测试用例生成中是通过区间运算的结果进行判断的,尤其是路径中的每一个约束条件都必须得到满足才能使整条路径可达,这是对区间运算进行优化的出发点。

下面用一个例子来说明面向路径的测试用例生成问题。图3-2所示为一个待测程序test1及其对应的控制流图,其中if_out_7、if_out_8、if_out_9、exit_10是虚节点。如果采用分支覆盖,则有4条待覆盖路径,即Path1:0→1→2→9→10(路径上的数字表示CFG的节点,下同)、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。令Path3为待覆盖路径(加粗显示部分),则我们的目标就是从{D 1,D 2,D 3}中为x 1、x 2和x 3选择一组值V={V 1,V 2,V 3},使得以{V 1,V 2,V 3}为输入执行test1时所经过的路径为Path3。Path3上有3个分支节点if_head_1、if_head_3和if_head_5,还有相应的3个分支F_2、F_4和T_5包含着要满足的约束。(https://www.daowen.com)

图3-2　待测程序test1及其对应的控制流图