5.2.7　实例分析

本节以算法5-3中的程序为例,对比利用反向和正向不可达路径判定方法为包含LDc2的程序生成可达路径的过程。位于真分支的条件语句8的语句9被选为覆盖目标,变量i在循环的每一次迭代中进行累加,累加的数值由i的奇偶性决定,循环的结束条件与i的取值相关。为了简化的目的,循环中只保留了与条件语句“if(i%2==0)”具有条件依赖和数据依赖的部分,可以看出此段代码符合LDc2的定义。为了执行到目标语句,循环至少需要执行6次(i=9,n=20)。

利用正向和反向符号执行技术生成可达路径的搜索过程示意如图5-12所示,图中的边表示约束和操作,方框中代表满足入边约束的变量取值范围。

左侧表示反向分析的过程,目标语句“if(i==20)”的真分支的条件被用来作为优化约束的前缀条件,然后沿着两个可能的分支i=i+3和i=i+1继续搜索,根据反运算得出变量i在经过两条操作语句之前的值相应为17或19,由于这两条语句分别对应着判定i是奇数和偶数,此时几个条件组成了矛盾的分支关联关系,因此可将此条路径抛弃,沿着条件为奇数的分支继续搜索。在反向分析循环的每一次迭代中,都可以判定出一个无法满足的分支条件。(https://www.daowen.com)

图5-12　使用反向分析和正向分析生成可达路径的搜索过程示意图

相反的,在右侧的正向分析过程中,由于输入域是多个值,因此循环的每一次迭代都无法进行剪枝,所以搜索空间的规模要大于反向分析的搜索空间。

这个实例说明,对于包含LDc2的程序,利用反向不可达路径判定技术来生成可达路径的效率比正向分析的效率要高。