3.1.2 解决方案
因为面向路径的测试用例生成问题是一类约束满足问题,这类问题需要通过合适的搜索或寻优算法来求解。分支限界作为全局求解算法提供灵活的回溯机制,可以在局部无解时回到更高的层次,以调整搜索的范围并尽量减少访问搜索树上节点的数量。由于回溯操作会增加算法的时间复杂度,因此需要合适的规则扩展叶子节点,包括合理对自由变量进行排序、在尽量少的次数内给变量找到可行解或者尽快判断局部无解,以及在找到可行解后尽量多地剪枝。因为面向路径的测试用例生成只要有一组解即可,所以在搜索过程中不需要生成可扩展节点的全部孩子节点,只要判断一个孩子节点可扩展就可以继续向下进行搜索,这样也可以提高算法执行的效率。这个进行扩展的孩子节点被认为是某种意义下的最优孩子节点,所以我们提出了使用最佳优先搜索的分支限界法(Best-First-Search with Branch and Bound,BFS-BB)进行求解。为了简便起见,分支限界与BFS-BB所指的都是我们使用的全局搜索算法,在本书中两者是等价的。
本节中提到的变量都是符号变量。在搜索过程中,变量被分成3个集合:已赋值变量(Past Variable,PV)、当前变量(Current Variable,CV)和未赋值变量或自由变量(Future Variable,FV)。
1.状态空间搜索
定义3-1 搜索的状态空间是一个四元组(S,A,I,F),其中S是状态的集合;A是状态之间的连接,代表搜索在不同状态的操作;I是S的一个非空子集,代表问题的初始状态;F是S的一个非空子集,代表问题的最终状态。
定义3-2 状态是一个五元组(Precursor,Variable,Domain,Value,Type)。当搜索进行到某一阶段的时候,对于当前状态S cur,Precursor是其前驱状态;当前变量Variable=X i∈X(i=1,2,…,n)是被测程序的一个输入变量;Domain=D ij⊆Di∈D(i=1,2,…,n;j=1,2,…,m)是当前变量的区间,即可能为x i所赋值的集合,其形式为[min,max],min和max分别是其下界和上界,n是变量数量即搜索树的深度,m是在其他变量保持不变的条件下,可以为当前变量进行赋值的次数上限,用于控制搜索树的宽度;Value=V ij∈Dij是从Domain中选出并赋给x i的值;Type是状态的类型,包括active(活跃)、extensive(可扩展)或inactive(休止)。
定义3-3 状态空间搜索是指在状态空间(可能会非常庞大)中找到一个最终状态,在这个最终状态中每一个变量都被赋予了一个确定的值并且验证出这些确定值是问题的一个解。搜索开始时Precursor为null;搜索结束时Variable为null,所有的extensive节点构成了解路径。
测试用例生成的过程在本书中就是状态空间搜索的过程。在状态空间中,我们需要从初始状态出发,在每个当前状态下,通过智能化的方法找到可能的搜索方向,并找到到达最终状态的解路径。
2.BFS-BB(https://www.daowen.com)
首先将本书中出现的一些算法和对它们的描述列在表3-1中。接下来是对算法及其伪代码的介绍。
表3-1 本书中的一些算法及其描述
第一阶段进行预处理操作。首先是预处理工作,包括路径约束的提取、确定相关变量集和相关变量闭包、确定变量级别。通过移除不相关变量(IVR)对搜索空间进行压缩,只保留与待覆盖路径相关的变量作为算法操作的对象。然后扫描路径约束,使用程序切片技术对变量区间进行压缩。存储测试用例的表result为空。对所有相关变量进行排序得到队列,它的队首元素x 1成为第一个要被赋值的变量。从x 1的区间D 11中为其选取V 11进行赋值。以上这些元素构成了初始状态(null,x 1,D 11,V 11,active),也就是当前状态S cur。
第二阶段进行状态空间搜索。这一阶段主要是调用爬山法对对应于变量x i的活跃状态(Pre,x i,Dij,V ij,active)进行判断。具体说来,爬山法会对变量的区间进行区间运算,并通过区间运算的结果来决定下一步搜索的方向。如果区间运算成功了,则到达山顶,Type转变成extensive,更新FV返回下一个待赋值变量并成为下一状态的当前变量,S cur变成Precursor。以上这些元素构成一个新状态,继续对其调用爬山法进行判断。如果在一次成功的区间运算后,FV中再无变量需要进行排序,则意味着所有的相关变量都已经被赋予了一个确定值,并且这组确定值使得路径p可达。最后给所有的不相关变量赋以随机值就完成了测试用例result的生成。
如果某次区间运算失败了,则对失败信息进行分析,计算目标函数值并对D ij进行削减,重新为x i在削减后的区间中选择一个值,调用爬山法进行判断,以上这些意味着搜索在搜索树上横向展开。如果当前变量区间内的所有值都被穷举完毕,或者为当前状态进行的区间运算已经达到次数上限m(控制搜索树宽度的阈值),则Type转变成inactive,这意味着搜索将回溯到位于搜索树上一层的Precursor。
