Computer Science ›› 2018, Vol. 45 ›› Issue (1): 255-260.doi: 10.11896/j.issn.1002-137X.2018.01.045

Previous Articles     Next Articles

Symbolic ZBDD-based Generation Algorithm for Combinatorial Testing

HUANG Yu-yao, LI Feng-ying, CHANG Liang and MENG Yu   

  • Online:2018-01-15 Published:2018-11-13

Abstract: 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.

Key words: Combinatorial testing,Zero-suppressed binary decision diagram,T-wise coverage,Test case generation

[1] KUHN D R,REILLY M J.An Investigation of the Applicability of Design of Experiments to Software Testing[C]∥Software Engineering Workshop,2002.NASA Goddard/IEEE,2002:91.
[2] DUNIETZL I S,MALLOWS C L,IANNINO A,et al.Applying Design of Experiments to Software Testing[C]∥International Conference on Software Engineering.1997:205-215.
[3] WILLAMS A W,PROBERT R L.A Practical Strategy for Testing Pair-wise Coverage of Network Interfaces[C]∥InternationalSymposium on Software Reliability Engineering,1996.IEEE,1996:246-254.
[4] COHEN M B,GIBBONS P B,MUGRIDGE W B,et al.Constructing Test Suites for Interaction Testing[C]∥International Conference on Software Engineering.IEEE,2003:38-48.
[5] COHEN D M,DALAL S R,FREDMAN M L,et al.The AETG System:An Approach to Testing Based on Combinatorial Design[J].IEEE Transactions on Software Engineering,1997,3(7):437-444.
[6] COHEN D M,DALA S R,KAJLA A,et al.The Automatic Efficient Test Generator (AETG) system[C]∥ Proceeding of 5th International Symposium on Software Reliability Engineering,1994.1994:303-309.
[7] COHEN D M,DALA S R,PARELIUS J,et al.The Combinatorial Design Approach to Automatic Test Generation[J].IEEE Software,1996,13(5):83-88.
[8] TAI K C,LIE Y.A Test Generation Strategy for Pairwise Testing[J].IEEE Transactions on Software Engineering,2002,28(1):109-111.
[9] KUHN R,LEI Y,KACKER R.Practical Combinatorial Tes-ting:Beyond Pairwise[J].It Professional,2008,10(3):19-23.
[10] CZERWONKA J.Pairwise Testing in Real World Practical Extensions to Test Case Generators.
[11] SEGALL I,TZOREF-BRILL R,FARCHI E.Using binary decision diagrams for combinatorial test design[C]∥International Symposium on Software Testing and Analysis(ISSTA 2011).Toronto,Canada,2011:254-264.
[12] BRYAN R E.Symblic Boolean Manipulation with Ordered Binary Decision Diagram[J].ACM Computing Surveys,1992,24(3):293-318
[14] MINATO S.Zero-suppressed BDDs and Their Applications [J].International Journal on Software Tools for Technology Transfer,2001,3(2):156-170.
[15] LI F Y,GU T L,CHANG L,et al.Timed Petri and ZBDD Based Approach for Assembly Sequence Planning[J].Computer Scien-ce,2012,39(2):170-174.(in Chinese) 李凤英,古天龙,常亮,等.一种基于赋.Petri网和ZBDD 的装配序列规划方法[J].计算机科学,2012,9(2):170-174.
[16] WANG Y,NIE C H,ZHANG S B.An Empirical Study of the Combinatorial Testing of Time-shifted TV Programs[J].Computer Engineering and Science,2015,37(5):958-966.(in Chinese) 王燕,聂长海,张少兵.面向时移电视类业务的组合测试实践研究[J].计算机工程与科学,2015,37(5):958-966.
[17] CHEN H,WANG S Y,PAN X Y.Pairwise Combinatorial Testing Suite Global Optimization and GenerationMethod[J].Computer Engineering and Applications,2012,48(11):32-36.(in Chinese) 陈皓,王曙燕,潘晓英.成对组合测试数据的整体优化和生成方法[J].计算机工程与应用,2012,48(11):32-36.
[18] GARGANTINI A.Efficient Combinatorial Test Generation basedon Multivalued Decision Diagrams[M]∥Hardware and Software:Verification and Testing.Springer International Publi-shing,2014:220-235.
[19] MINATO S I.Graph-Based Representations of Discrete Functions[M]∥Representations of Discrete Functions.Springer US,1996:1-28.
[20] COEHN M B,GIBBONS P B,MUGRIDGE W B,et al.Constructing Test Suites for Interaction Testing[C]∥International Conference on Software Engineering.IEEE,2003:38-48.
[21] NIE C,LEUNG H.A survey of combinatorial testing[J].Acm Computing Surveys,2011,43(2):33-63.
[22] YAN J,ZHANG J.Combinatorial testing:Principles and me-thods[J].Journal of Software,2009,0(6):1393-1405.(in Chinese) 严俊,张健.组合测试:原理与方法[J].软件学报,2009,20(6):1393-1405.
[23] SPICHKOVA M,ZAMANSKY A.A Human-CentredFrame-work for Combinatorial Test Design[C]∥International Conferen-ce on Evaluation of Novel Approaches To Software Enginee-ring.2016.
[24] CHENG C,DUMITRESCU A,SCHROEDER P.GeneratingSmall Combinatorial Test Suites to Cover Input-output Relationships[C]∥ International Conference on Quality Software.2004:76-82.
[25] KUHN D R,KACKER R N,LEI Y.Practical Combinatorial Testing.
[26] SAHL A N,ALSARIERA Y A,ZAMLI K.Late Acceptance Hill Climbing Based Strategy for Addressing Constrain Within Combinatorial Test Data Generation[C]∥The 7th edition of Annual Software Testing Conference,2014.2014.
[27] KUHN D R,KACKER R N,YU L.Measuring and specifying combinatorial coverage of test input configurations[J].Innovations in Systems & Software Engineering,2015,12(4):1-13.

No related articles found!
Full text



No Suggested Reading articles found!