Software Testing Recent Summary (JPF ETC)

首先通过讲解object – oriented 类型代码的测试 讲到了我们如果要创建一个只有两个节点的rep ok的acyclic list,一共有7种方式

针对这种以面向对象作为基准的数据结构,我们首先测试了add函数,测试add函数的时候我们有两种方式,一种方式是直接利用add函数进行初始化 另外一种方式是通过初始化指定的field对节点进行初始化,然后在仅仅调用一次add函数进行repok的检查

因为我们对repok的要求是至多有两个节点,并且每一个节点本身的值只能是0 或者 1 所以我们从抽象的操作角度可以对其采用下面形式的初始化

所以为了能够实现complete的coverage 我们不得不机械地完成21个test case,所以这个时候我们变希望能够利用一种工具完成non – deterministic 的状态初始化


其中比较反直觉的操作是,我们使用getint操作的时候 作为boundry的min 和 max value 都可以直接获取,这一点其实可以从getBoolean 操作进行理解,意味getBoolean操作要求能够同时返回true 和 false才能保证我们覆盖足够多的state

所以上面的代码可以被简化为


接下来我们就要对jpf进行更进一步的讨论, 这一部分将是final exam的重要部分

  1. 首先jpf 是完全回溯的,它是一种jvm级别的实现方式,相当于在每一次进入到不同的状态的时候,jvm虚拟机就会保存之前的状态,其中包含所有的静态变量。所以说如果我想统计在jvm的遍历过程中一共进行了多少次执行,是无法利用一格静态变量进行统计的。因为在回溯的过程中,一旦回到了根节点,所有的状态都会返回到最初的状态,也就是我们声明的静态变量 static int count = 0 不会得到改变
  2. 所以解决上面这个问题的方法是使用jpf自带的listener mechanism. 具体的方法是使用Verify.ResetControl 或者 Verify.AddCount 这种系统自带的API进行统计

  3. 例如上面讲到的resetCounter操作就可以将counter重新置为0 然后处于Verify下面的静态方法 incrementCounter(0) 就可以显示出当前的counter中统计的计数数量.最后发现上面jpf执行的次数统计依然是21,和我们最开始在abstract level的表示方法是一致的

  4. 除此之外,如果我们希望jpf来选择一些non – deterministic的state,这些state如果不是连续的,我们可以将state存储在数组中,用jpf来随机生成对应的下标进行访问,而不是选择复杂的continue语句

但是上面的add remove操作来生成链表本质上还是属于采用基于代码的实现方式,如果我们需要实现representation级别的un detemerministic 这个时候采用的方法就会有所不同,因为要避免很多无关的state


header 和 size都有3中选择 所以是9 中间没有节点考虑到 elem 和 next 后 发现作为一个组合最后的结果都是6 所以最终的答案是 9 * 6 * 6

为了完整地实现所有的non-deterministic state, 我们最开始选择的标识方式为

其中采用的技巧就是我们之前谈到的,利用jpf来获得数组的下标,然后选取相应的元素

但是这个过程中势必会带来很多冗余,其中对于冗余情况的分析是:


因为其中很多情况下,如果一开始头结点已经选择为null 了 后面节点的所有初始化操作都是没有意义的,毕竟我们最后只有7个情况需要考虑

具体来说,我们可以在size 等于0的时候 直接中止后继程序的执行,也就是不再做任何初始化的操作,

但是如果采用这种方法,我们只能在某些非常特定的case 上进行优化,并没有办法实现全局的优化,所以我们采用的一个方法是只有当repok要进行access某些field的时候才对这些field进行赋值,进行jpf的搜索过程

指导思想是利用repok函数来完成剪枝

例如从下面的boolean 函数 就可以发现 只要当条件触法到我需要使用倒着写变量的时候,我才会调用jpf的getint或者其他get函数进行non-deterministic的初始化


关键是分析函数执行到什么步骤的时候才需要access对应的变量

这样的剪枝是显著的,也就是如果header 是null 就停止所有的考虑的时候,剪枝分叉的所有路径都会消失

通过上面的方法进行剪枝的效果如上图所示

并且根据虚拟机生成的机器码,我们可以用专业的软件进行进一步的搜索剪枝优化,就好比在backtracking中回溯到之前的状态的时候,如果发现已经没有继续搜索的必要的话,就可以直接停止所有的操作

所以说这种优化方式尝尝发生在backtracking中

再次强调基本思想:我们的目标是在满足repok的条件下,创建只有两个node value 为0 或者1 的链表,所以我们可以再repok需要访问某些field的时候(注意我们现在是representation的表示方法)在对相应的field进行初始化操作

Advertisements