2021/05/12 by Muhammad Ashfaq, Rubing Huang, Dave Towey +4 · 9 citations
Computer Science · #Cluster analysis #Consistency (knowledge bases) #Curse of dimensionality #Graph #Orthogonal array testing #Overhead (engineering) #Random testing #Software #Software Reliability and Analysis Research #Software System Performance and Reliability #Software Testing and Debugging Techniques #Test case #cs.SE
paper · pdf · doi:10.1016/j.jss.2021.111008
published in Journal of Systems and Software 180, 111008 (Elsevier BV) · 26 Pages
arxiv created 2021/05/12 · openalex created_date 2021/05/24 · openalex publication_date 2021/05/27 · arxiv updated 2021/06/01 · openalex updated_date 2026/08/05
Adaptive random testing (ART) improves the failure-detection effectiveness of random testing by leveraging properties of the clustering of failure-causing inputs of most faulty programs: ART uses a sampling mechanism that evenly spreads test cases within a software's input domain. The widely-used Fixed-Sized-Candidate-Set ART (FSCS-ART) sampling strategy faces a quadratic time cost, which worsens as the dimensionality of the software input domain increases. In this paper, we propose an approach based on small world graphs that can enhance the computational efficiency of FSCS-ART: SWFC-ART. To efficiently perform nearest neighbor queries for candidate test cases, SWFC-ART incrementally constructs a hierarchical navigable small world graph for previously executed, non-failure-causing test cases. Moreover, SWFC-ART has shown consistency in programs with high dimensional input domains. Our simulation and empirical studies show that SWFC-ART reduces the computational overhead of FSCS-ART from quadratic to log-linear order while maintaining the failure-detection effectiveness of FSCS-ART, and remaining consistent in high dimensional input domains. We recommend using SWFC-ART in practical software testing scenarios, where real-life programs often have high dimensional input domains and low failure rates.