An experimental study of neighbourhood based metaheuristic algorithms for test case generation satisfying the modified condition / decision coverage criterion

• Main Author: Haque, Ariful
• Format: Thesis
• Language: English
• Published: 2018
• Subjects: QA76 Computer software
• Online Access: http://umpir.ump.edu.my/id/eprint/24801/1/An%20experimental%20study%20of%20neighbourhood%20based%20metaheuristic%20algorithms%20for%20test%20case%20generation%20satisfying%20the%20modified%20condition-decision%20coverage%20criterion.wm.pdf; http://umpir.ump.edu.my/id/eprint/24801/

Software testing is an important part of software development as it ensures the proper functionality of software and reduces the risk of failure. In the case when software is being adopted in a mission critical application, failure can lead to loss of life and fortunes. Therefore, it is mandatory to test all possible functional paths of the software exhaustively. Exhaustive testing is costly and time consuming and with the higher number of inputs, the number of test cases increases exponentially. Many researchers suggested the adoption of Modified Condition / Decision Coverage (MC/DC) criterion as a solution to the problem particularly when the inputs involve Boolean variables. Often, MC/DC can reduce the number of test cases dramatically and ensure critical paths are tested. To generate test cases that satisfy MC/DC criterion, many researchers adopt neighborhood based meta-heuristics algorithms (including that of Simulated Annealing and Hill Climbing) as the problem itself is neighborhood based. Although useful, the existing algorithms does not provide any comparative data to select an algorithm based on the problem size and difficulty and the use of other neighborhood algorithms (including Great Deluge and Late Acceptance Hill Climbing) has not been sufficiently explored as well. In order to identify the strength and weakness of these algorithms for MC/DC compliant test cases, this research proposes an experimental study involving four neighborhoods based meta-heuristic algorithms. We have chosen four neighborhood based algorithms which are commonly used in optimization problems and divided them in newly implemented and re-implemented category. Late Acceptance Hill Climbing (LAHC) and the Great Deluge Algorithm (GDA) which are our new implementation, Simulated Annealing (SA) and Hill Climbing (HC) are re-implemented to generate test cases satisfying MC/DC criterion for comparative analysis. The algorithms are used to generate test cases for nine different Boolean expressions of different size and complexities. Performance of each algorithm is compared in terms of number of test cases generated as well as the run time required. Our experience indicates that all the algorithms generate nearly similar number of test cases, but in terms of performance, they differ from one another. The elaborated result of the study will help test engineers to choose the algorithm they need to generate test cases efficiently and optimally.