Adaptive random testing (ART) achieves better failuredetection effectiveness than random testing by increasing the diversity of test cases. However, the intention of ensuring even spread of test cases inevitably causes an overhead problem. Although two basic forgetting strategies (i.e. random forgetting and consecutive retention) were proposed to reduce the computation cost of ART, they only considered the temporal distribution of test cases. In the paper, we presented a distanceaware forgetting strategy for the fixed size candidate set version of ART (DFFSCS), in which the spatial distribution of test cases is taken into consideration. For a given candidate, the test cases out of its “sight" are ignored to reduce the distance computation cost. At the same time, the dynamic adjustment for partitioning and the secondround forgetting are adopted to ensure the linear complexity of DFFSCS algorithm. Both simulation analysis and empirical study are employed to investigate the efficiency and effectiveness of DFFSCS. The experimental results show that DFFSCS significantly outperforms the classical ART algorithm FSCSART in efficiency, and has comparable failuredetection effectiveness. Compared with two basic forgetting methods, DFFSCS is better in both efficiency and effectiveness. In contrast with a typical lineartime ART algorithm RBCVTFast, our algorithm requires less computational overhead and exhibits the similar failuredetection capability. In addition, DFFSCS has more reliable performance than RBCVTFast in detecting failures for the programs with highdimensional input domain.
Figure 1
The typical failure patterns in a twodimensional input domain. Here, the shaded areas represent failurecausing inputs. (a) Block pattern; (b) strip pattern; (c) point pattern.
Figure 2
An illustration of distanceaware forgetting strategy for ART. (a) The basic FSCSART; (b) distance computation within the sight of candidate point $c_k$.
Figure 3
(Color online) The trend of the average computation overhead $\overline{C}_\text{DFFSCS}$. Here, the parameters are set as follows: $\varphi_0=9$, $\tau=5$, $d=2$, $s=10$. (a) $n$ from 0 to $10^4$; (b) $n$ from 0 to $10^6$.
Figure 4
(Color online) The overhead comparison on five algorithms ($n$ from 0 to $2\times 10^4$). (a) DFFSCS vs. FSCSART vs. RBCVTFast; (b) DFFSCS vs. RFFSCS vs. CRFSCS.
Figure 5
(Color online) The Pmeasureresults of all 12 programs. (a) airy ($d=1$); (b) bessj0 ($d=1$); (c) erfcc ($d=1$); (d) probks ($d=1$); (e) tanh ($d=1$); (f) bessj ($d=2$); (g) gammq ($d=2$); (h) sncndn ($d=2$); (i) golden ($d=3$); (j) plgndr ($d=3$); (k) cel ($d=4$); (l) el2 ($d=4$).
Figure 6
(Color online) The Pmeasureresults in different values of parameter $\alpha$ in RBCVTFast algorithm. (a) cel ($d=4$); (b) el2 ($d=4$).
Input parameters $s$, $d$, $p_0$ and $\tau$; 
Set $p=p_0$, $n=0$, $t=0$ and $\text{TS}=\{\}$; 
Partition each dimension into $p_0$ equal parts, $\varphi_0=p_0^d$, and construct a corresponding indexing structure for cells; 
Randomly select a test case $\text{tc}$ from the input domain; 
Add $\text{tc}$ into $\text{TS}$, and increment $n$ by 1; 
Localize the cell of $\text{tc}$, and add $\text{tc}$ into the indexing structure; //dynamic adjustment for partitioning from line 8 to 12 

$p=2p$, $t=t+1$; 
Repartition each dimension into $p$ equal parts, and construct a new indexing structure for it; 
Relocate all test cases in $\text{TS}$ into the new indexing structure; 

Randomly generate $s$ candidates $c_1, c_2, \dots, c_s$ from the input domain; 

Localize the cell of $c_k$, and find its neighbour region $\text{neig}(c_k)$ according to ( 
Collect all test cases lying in $\text{neig}(c_k)$ to from set $\text{TS}_{\text{neig}(c_k)}$; 

$\textrm{tc}=c_k$; 


Call 

Calculate the distance from $c_k$ to $\text{tc}_j$, and denote it as $d_{kj}$; 

Find the shortest one from $\{d_{kj}\} (1\leq j\leq \text{TS}^\text{up}_{\text{neig}(c_k)})$, and denote it as $\text{dist}_\text{ap}(c_k, \textrm{TS})$; 

Find the candidate whose $\text{dist}_\text{ap}(c_k, \textrm{TS}) (1\leq k\leq s)$ is the largest one, and set it as $\text{tc}$; 
Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有
京ICP备18024590号1