基于符号零压缩二叉决策图的组合测试用例生成方法

Symbolic ZBDD-based Generation Algorithm for Combinatorial Testing

组合测试是系统测试中一种非常有效的方法,能够在保证错误检出率的前提下采用较少的测试用例来测试系统。但是,组合测试用例集构造问题的复杂度是NP完全的。给出了一种基于符号零压缩二叉决策图(Zero-suppressed Binary Decision Diagram,ZBDD)的组合测试用例生成方法。该方法首先利用ZBDD的结构特性,对测试系统进行紧凑的符号表示。然后利用ZBDD的隐式操作,结合贪心算法的思想,不断地覆盖更多的组合并缩小未覆盖组合集合,生成2~4维覆盖强度的较小测试用例集。实验证明,所提方法不仅可行而且节点开销小。

Combinatorial testing is an effective method in system testing,which can test system with fewer test cases under the premise of guaranteeing error detection rate.However,the complexity of the problem of constructing test cases is NP-complete,and many algorithms only get the suboptimal solution.This paper presented a method of generating test cases based on symbolic Zero-suppressed binary decision diagram(ZBDD).The method first uses the structure of ZBDD to perform a compact symbolic representation of the test system.Then,using implicit operations of ZBDD and combining with the idea of greedy algorithm,the method can cover more combinations and reduce the set of uncover combinations to generate smaller set of test cases.The method can satisfy 2 to 4 wise coverage.Experiments show that this method is feasible and has the characteristic of small node cost.