2019/07/03 by Tatsuhiro Tsuchiya, Tsuchiya, Tatsuhiro
Computer Science · #68M15 #68N30 #FOS: Computer and information sciences #Formal Methods in Verification #Software Engineering (cs.SE) #Software Engineering Research #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.1907.01779
openalex publication_date 2019/07/03 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Constraints among test parameters often have substantial effects on the\nperformance of test case generation for combinatorial interaction testing. This\npaper investigates the effectiveness of the use of Binary Decision Diagrams\n(BDDs) for constraint handling. BDDs are a data structure used to represent and\nmanipulate Boolean functions. The core role of a constraint handler is to\nperform a check to determine if a partial test case with unspecified parameter\nvalues satisfies the constraints. In the course of generating a test suite,\nthis check is executed a number of times; thus the efficiency of the check\nsignificantly affects the overall time required for test case generation. In\nthe paper, we study two different approaches. The first approach performs this\ncheck by computing the logical AND of Boolean functions that represent all\nconstraint-satisfying full test cases and a given partial test case. The second\napproach uses a new technique to construct a BDD that represents all\nconstraint-satisfying partial test cases. With this BDD, the check can be\nperformed by simply traversing the BDD from the root to a sink. We developed a\nprogram that incorporates both approaches into IPOG, a well-known test case\ngeneration algorithm. Using this program, we empirically evaluate the\nperformance of these BDD-based constraint handling approaches using a total of\n62 problem instances. In the evaluation, the two approaches are compared with\nthree different constraint handling approaches, namely, those based on Boolean\nsatisfiability (SAT) solving, Minimum Forbidden Tuples (MFTs), and Constraint\nSatisfiction Problem (CSP) solving. The results of the evaluation show that the\ntwo BDD-based approaches usually outperform the other constraint handling\ntechniques and that the BDD-based approach using the new technique exhibits\nbest performance.\n