Abstract
<italic>Adaptive random testing</italic> (ART) is an enhancement of <italic>random testing</italic> (RT), and aims to improve the RT failure-detection effectiveness by distributing test cases more evenly in the input domain. Many ART algorithms have been proposed, with <italic>fixed-size-candidate-set</italic> ART (FSCS-ART) being one of the most effective and popular. FSCS-ART ensures high failure-detection effectiveness by selecting as the next test case the candidate farthest from previously executed test cases. Although FSCS-ART has good failure-detection effectiveness, it also faces some challenges, including heavy computational overheads. In this article, we propose an enhanced version of FSCS-ART, <italic>vantage point partitioning ART</italic> (VPP-ART). VPP-ART addresses the FSCS-ART computational overhead problem using VPP, while maintaining the failure-detection effectiveness. VPP-ART partitions the input domain space using a <italic>modified vantage point tree</italic> (VP-tree) and finds the approximate nearest executed test cases of a candidate test case in the partitioned subdomains—thereby significantly reducing the time overheads compared with the searches required for FSCS-ART. To enable the FSCS-ART dynamic insertion process, we modify the traditional VP-tree to support dynamic data. The simulation results show that VPP-ART has a much lower time overhead compared to FSCS-ART, but also delivers similar (or better) failure-detection effectiveness, especially in the higher dimensional input domains. According to statistical analyses, VPP-ART can improve on the FSCS-ART failure-detection effectiveness by approximately 50–58%. VPP-ART also compares favorably with the <italic>KD-tree-enhanced fixed-size-candidate-set ART</italic> (KDFC-ART) algorithms (a series of enhanced ART algorithms based on the KD-tree). Our experiments also show that VPP-ART is more cost-effective than FSCS-ART and KDFC-ART.
Original language | English |
---|---|
Pages (from-to) | 1-16 |
Number of pages | 16 |
Journal | IEEE Transactions on Reliability |
DOIs | |
Publication status | Accepted/In press - 2022 |
Keywords
- adaptive random testing (ART)
- approximate nearest neighbor
- Software testing
- vantage point partitioning (VPP)
- vantage point tree (VP-tree)
ASJC Scopus subject areas
- Safety, Risk, Reliability and Quality
- Electrical and Electronic Engineering