Automatic Determination of Branch Correlations in Software Testing

Path-oriented testing is an important aspect of software testing. A challenging problem with path-oriented test data generation is the existence of infeasible paths. Timely detecting these infeasible paths can not only save test sources but also improve test efficiency. It is an effective method to detect infeasible paths by branch correlations. In this paper, we propose a method to automatically determine branch correlations in software testing. Firstly, we give a theorem to determine the true-true correlation, true-false correlation, false-true correlation, and false-false correlation based on the probabilities of the conditional distribution corresponding to different branches´ outcome (i.e. true or false). We then estimate these values of the probabilities by the maximum likelihood estimation. Finally, we apply the proposed method to determine the branch correlations of two typical programs, and the results show that the proposed method can accurately determine the branch correlations of different conditional statements. Our achievement provides an effective and automatic method to detect infeasible paths, which has great significance in improving the efficiency of software testing.