Model-based Test Suite Generation for Fault Localization using Search-based Mutation Testing Technique

Abstract

Software testing is gradually becoming a more important part of software development as the complexity of software increases. Significant amounts of time and manpower are required to conduct tests manually, so automated testing is considered essential. Model-based testing (MBT) is one of several methods for generating test data. Transition coverage testing, a testing technique using state charts of Unified Modeling Language (UML), requires generation of transition paths that cover all transitions. Several automatic transition path generation studies have been conducted using genetic algorithms (GAs), but when generating a transition path using a GA, the dependent transition pairs serve as distractions. Furthermore, counter problems that require repeated execution of dependent transitions (for example, to test a failing operation of an automatic teller machine, the password must be incorrect three times) make feasible transition path (FTP) generation more difficult.

Debugging is also an important part of software testing. Fault localization techniques reduce the effort required when debugging software, as revealed by previous test cases. However, many test cases are required to reduce the number of candidate fault locations. To overcome this disadvantage, various methods have been proposed to reduce fault-localization costs by prioritizing test cases. However, because a sufficient number of test cases is required for prioritization, the test-case generation cost remains high.

This thesis proposes a test case generation method using a state chart to reduce the number of test suites required for fault localization, minimizing the test-case generation and execution times. The test-suite generation process features two phases: feasible path generation and test data generation for fault localization. The first phase uses grouping genetic algorithm (GGA) to generate feasible transition path. The second phase uses mutation analysis to evaluate test cases; the results are employed to improve the test cases, using genetic algorithms.

To verify that FTP generation is available, experiments using the ‘inres initiator’ state chart and the ‘automatic teller machine’ state chart generated FTPs successfully. In the case of the inres initiator state chart, the proposed GGA was shown to be capable of generating FTPs with a 100% coverage. In the case of the ATM state chart, the proposed GGA was shown to be capable of generating FTPs with a 100% coverage, by setting the maximum number of generations.

To confirm the effectiveness of the test data generation for fault localization, four levels of faults were inserted into four types of state charts; thus, 16 faulty versions of state charts were used in the experiments. The experimental results confirmed that the method that used the Jaccard distance was more effective than the method that used lookahead entropy, and the suspiciousness of faulty statements increased by more than 21% compared to random test suites based on boundary values.

This thesis provide useful guidelines for application of a search based mutational method to a state chart; It show that the proposed method improves fault localization performance in the test-suite generation phase.