Enhancing The Efficiency Of Adaptive Random Testing By Nearest Neighbor Algorithms

Software testing is a fundamental software quality assurance activity that eventually leads to better-engineered software.Random testing(RT)is a popular software testing technique that randomly selects and executes a subset of test cases from the software's input domain.Adaptive random testing(ART)aims to improve RT by leveraging properties of the clustering of failurecausing inputs of most faulty programs: ART uses a sampling mechanism that evenly spreads test cases within the software's input domain.The widely-used,highly effective,and relatively simple ART sampling strategy Fixed-Sized-Candidate-Set ART(FSCS-ART)faces a quadratic time cost,which becomes prohibitive in high dimensions.As most real-world programs have high dimensional input domains and low failure rates,this problem should be addressed.This thesis aims to solve the efficiency problem of FSCS-ART while preserving its failuredetection effectiveness.We identify FSCS-ART as an instance of the Nearest Neighbor Search(NNS)problem and hypothesize that FSCS-ART's efficiency problem lies in its NNS mechanism.If the NNS mechanism can be scalable and consistent with dataset size and dimensions,it may alleviate the efficiency problem.Firstly,an approach based on small world graphs has been proposed,called 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,nonfailure-causing test cases.Moreover,SWFC-ART has shown consistency in programs with high dimensional input domains.The experimental 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.Secondly,CPU-level execution analysis of FSCS-ART has been performed and found out that FSCS-ART suffers from a prohibitive run-time cost mainly due to its Single-InstructionSingle-Data(SISD)mechanism for its distance calculation process.Consequently,a novel and efficient implementation of FSCS-ART has been proposed: FSCS using Single-InstructionMultiple-Data(FSCS-SIMD).FSCS-SIMD employs SIMD instruction architecture for simultaneous distance calculations of multiple test cases in a many-to-many fashion.The proposed method loads a batch of test cases from the candidate test case set and executed test case set in one CPU execution cycle.After that,a single distance calculation instruction is given to the whole batch for the calculation of all pairwise distances.A series of simulations and empirical studies show that,on average,FSCS-SIMD reduces test case generation overhead of FSCS-ART up to 90%,while maintaining similar failure detection effectiveness.Lastly,a method based on NNS using Quantization and Inverted File Index structure has been adopted to enhance FSCS-ART.The proposed method(called QIVFSCS-ART)preprocesses the software input domain by partitioning it into discrete cells by using k-means clustering relying on a uniform random dataset.Afterwards,the quantized form of each executed test input is stored in the inverted list of its cell's center,called centroid.Results show that the proposed method significantly relieves the computational overhead of FSCS-ART while preserving its failure-detection effectiveness,especially for the high-dimensional software input domains.