An Empirical Comparison of the Efficiency and Effectiveness of Genetic Algorithms and Adaptive Random Techniques in Data-Flow Testing

Abstract

Software Testing depends on the execution of the tested-program against a set of test-inputs and the comparison of its outputs with the expected ones. The size of the input domain is very large that can be the set of real numbers (R). Thus, the selection of the appropriate inputs is one of the key problems in software testing. This process is time-consuming and needs a lot of effort and budget. Therefore, automatic inputs generation techniques are required to overcome these problems. Genetic algorithms (GAs) have been successfully used for generating test-inputs. Researchers proved that GAs overcame ordinary random search techniques (ORTs) in generating inputs. In addition, GAs can converge faster than ordinary random techniques and they can reduce effectively the size of the test-suite. Unfortunately, technically GAs needs time more than ORTs. Adaptive random testing technique (ART) is a form of ORT that works for distributing test-cases more evenly through the input domain to increase the efficiency of ORTs. So far, there is no study comparing the efficiency of GAs and ARTs in data-flow testing. In this paper, we introduce an empirical comparison for genetic algorithms and adaptive random techniques according to four factors: reducing the size of the test-suite, convergence speed, elapsed time, and the effectiveness in maximizing the coverage ratio of all du-pairs criterion. The experimental study, which was conducted to compare the two techniques, contains 7 Java programs. The results of the experiments showed that the GA technique defeated the ORT technique and the ART technique in reducing the size of the required test-suite to satisfy all du-pairs criterion. Where the GA technique created in total 31532 test-inputs while the ART technique generated 61841 and the ORT technique produced 32064. Further, the results showed that the GA technique converged faster than the ORT technique and the ART technique. Where the procedure of the GA technique was repeated 3153 times totally while the procedure of the ART technique was iterated 6184 times and the procedure of the ORT technique was repeated 3206 times. In addition, the convergence rate of GA-based technique = 8.25 generations/second, the convergence rate of the ORT = 11.98 generations/second, and the convergence rate of the ART = 13.27 generations/second. Moreover, the results showed that the GA technique is faster than the ART technique and slower than the ORT technique. Where the GA technique consumed in total 382 seconds while the ART technique consumed 465.9 seconds and the ORT technique consumed 267.6 seconds. Additionally, the results showed that the GA technique satisfied overall coverage ratio equals 74% of all du-pairs while the ART technique satisfied 78% and the ORT technique satisfied 73%. From these results, we concluded that GA algorithms are more effective than ORT and ART techniques in data-flow testing but ART satisfied the most coverage ratio. Therefore, we recommend hybridizing GA and ART and applying the hybrid technique in the test-data generation process.

Keywords

• Adaptive random testing
• data-flow testing
• genetic algorithms
• test data generation