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

Symbolic ZBDD-based Generation Algorithm for Combinatorial Testing

作　　者：黄钰尧 李凤英[1] 常亮[1] 孟瑜[1] 

机构地区：[1]桂林电子科技大学广西可信软件重点实验室,广西桂林541004

出　　处：《计算机科学》2018年第1期255-260,共6页Computer Science

基　　金：广西自然科学基金项目(2016GXNSFAA380054);桂林电子科技大学研究生教育创新(YJCXS201541);广西高等学校高水平创新团队及卓越学者计划资助

摘　　要：组合测试是系统测试中一种非常有效的方法,能够在保证错误检出率的前提下采用较少的测试用例来测试系统。但是,组合测试用例集构造问题的复杂度是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.

关 键 词：组合测试 零压缩二叉决策图 覆盖强度 测试用例生成 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论]