Search

Similar paths are usually covered by similar test cases, which is one of the characteristics of automated test case generation for path coverage. Based on this characteristic, this paper proposes a novel search-based algorithm for generating test cases to satisfy path coverage criterion, called binary searching iterative algorithm. The proposed algorithm first selects an uncovered path as a target path, which is most similar to the path covered by a discovered test case. Then it performs a binary search in both the left and right regions of each element of the discovered test case under the guidance of a fitness function for the target path. Binary searching iterative algorithm can quickly find undiscovered test case covering the target path because of making full use of the characteristic of automated test case generation for path coverage. Experimental studies on six fog computing benchmark programs and six natural language processing benchmark programs show that the proposed algorithm can achieve the highest path coverage for all the twelve benchmark programs, and the average number of test cases obtained by the proposed algorithm is significantly less than those obtained by a number of state-of-the-art algorithms for eleven out of the twelve benchmark programs. Moreover, binary searching iterative algorithm is more appropriate for ALBD-based fitness function than BD-based fitness function.

Automated test case generation for path coverage (ATCG-PC), as an important task in software testing, aims to achieve the highest path coverage of a tested program by using as little computational overhead as possible. In ATCG-PC, “similar paths are usually executed by similar test cases” is a problem-specific knowledge which was touched by a handful of researchers but still underutilized. Inspired by the problem-specific knowledge, this paper designs a local search strategy by improving a scatter search strategy, and then proposes a grey prediction evolution algorithm with the improved scatter search strategy for ATCG-PC. Here, the improved scatter search strategy could obtain two feasible test cases by exploiting a dimension of a test case covering a certain path. The proposed algorithm is constructed by importing the improved scatter search strategy to the end of the reproduction operation of the grey prediction evolution algorithm holding strong exploration ability. Grey prediction evolution algorithm is first applied to solve ATCG-PC. The performance of the proposed algorithm is evaluated on six fog computing benchmark programs and six natural language processing benchmark programs. The experimental results demonstrate that the proposed algorithm can achieve the highest path coverage with the fewer test cases and running time than some state-of-the-art algorithms.