Combinatorial Test Case Generation Based on ROBDD and Improved Particle Swarm Optimization Algorithm

Abstract

In applications of software testing, the cause–effect graph method is an approach often used to design test cases by analyzing various combinations of inputs with a graphical approach. However, not all inputs have equal impacts on the results, and approaches based on exhaustive testing are generally time-consuming and laborious. As a statute-based software-testing method, combinatorial testing aims to select a small but effective number of test cases from the large space of all possible combinations of the input values for the software to be tested, and to generate a set of test cases with a high degree of coverage and high error detection capability. In this paper, the reduced ordered binary decision diagram is utilized to simplify the cause–effect graph so as to reduce the numbers of both the inputs and test cases, thereby saving the testing cost. In addition, an improved particle swarm optimization algorithm is proposed to significantly reduce the computation time needed to generate test cases. Experiments on several systems show that the proposed method can generate excellent results for test case generation.

Keywords

• test case generation
• reduced ordered binary decision diagram
• improved particle swarm optimization algorithm
• combinatorial test